The adsorption of oxygen on a Pd(1 1 0) surface has been studied with scanning tunneling microscopy (STM). The particular emphasis was given to the preparation of low oxygen coverages with the well known c(2 × 4)-O oxygen phase as a starting structure in the experiments. The oxygen content, surface morphology and structure were changed by annealing the sample to temperatures below the onset of oxygen desorption. The surface was characterized after cool-down to room temperature or temperatures in the range 100–140 K. At low temperatures we found a new oxygen adsorption structure characterized by a (3 × 2) periodicity. We also calculate the O/Pd(1 1 0) surface phase diagram by first-principles thermodynamics. For small coverages, near the low-coverage end of the large stability region of the c(2 × 4)-O structure it was found that a (2 × 3)-deep-O and a (2 × 3)-1D-O structures, which are degenerate in energy, are most stable. Conversely, at high chemical potentials, i.e. high coverages, a (7 × √3)-O structure becomes more stable. The formation of the metastable (3 × 2)-O phase is explained in terms of partial deoxidation via the interaction with residual hydrogen and by quenching of other types of restructuring at low temperatures since the (3 × 2)-O phase can be derived from the c(2 × 4)-O phase by slight rearrangement of oxygen atoms after the oxygen content was lowered from 1/2 to 1/3 of a monolayer. This is not the case with more stable structures of the same coverage which require an additional rearrangement of palladium atoms.