The structure of iodine adsorbed on a Pt(110) surface, formed by flame-annealing of the platinum crystal and quenching in iodine vapour, was investigated by scanning tunnelling microscopy (STM) in air and electrolyte solutions. We find that the (1 x 2) reconstruction is lifted and that a new structure is formed, characterized by a fourfold periodicity in [1(1) over bar0$] and extended rows in the [001] direction and a pronounced elongation of steps in the [001] direction. The STM data are in accord with the (4 x 1) low-energy electron diffraction pattern recorded after transfer of the sample to ultra-high vacuum. In H2SO4 and NaOH solutions the iodine was desorbed at negative potentials, resulting in an unreconstructed (1 x 1) surface and a change in surface topography towards small rectangular, more isotropic terraces.