Abstract The adsorbate-induced reconstructions of the Pd(110) surface during dissociative chemisorption of oxygen have been studied at elevated temperatures (between 400 and 520 K) by scanning tunnelling microscopy (STM). For relatively high exposures, a well-ordered c(2×4)-O overlayer is observed which consists of a Pd(1×2) added-row reconstruction decorated by oxygen adatoms. At 520 K this surface displays very little mobility, with defects and step edges remaining stationary over long time periods. For low exposures of oxygen, adsorption onto the clean surface at 430 K leads initially to the formation of a Pd(1×3) missing-row reconstruction which is again decorated by oxygen atoms. The decoration shows considerable disorder between the Pd rows, while along the rows the structure is relatively well ordered into a zig-zag chain. Structural models are proposed which satisfy both LEED and STM data and concur with coverages derived by other techniques.