We use photoelectron spectroscopy, low energy electron diffraction, scanning tunneling microscopy, and density functional theory to investigate coverage dependent iodine structures on Pd(110). At 0.5 ML (monolayer), a c(2 x 2) structure is formed with iodine occupying the four-fold hollow site. At increasing coverage, the iodine layer compresses into a quasi-hexagonal structure at 2/3 ML, with iodine occupying both hollow and long bridge positions. There is a substantial difference in electronic structure between these two iodine sites, with a higher electron density on the bridge bonded iodine. In addition, numerous positively charged iodine near vacancies are found along the domain walls. These different electronic structures will have an impact on the chemical properties of these iodine atoms within the layer.