The adsorption of CO on an oxygen precovered Pd(111) surface was investigated between 60 and 300 K. Applied methods were variable temperature scanning tunneling microscopy (STM) and video STM to analyze the coadsorption structures. The STM data are compared with simulated STM images for the various surface phases in order to identify the appropiate structural model for each case. Low-energy electron diffraction and reaction isotherms by means of mass spectrometry were used to correlate the phases with the reaction yielding CO2. The video-STM data recorded during CO adsorption at 300 K on the (2 X 2)0 phase show a fast phase transition into the (root 3 X root 3)R30(O)degrees structure, followed by reaction to CO2. The reaction only starts after completion of the phase transition, indicating that the (root 3 X root 3)R30(O)degrees structure plays a crucial role for the reaction. At temperatures between 170 and 190 K the phase transition is slow enough to be monitored with STM. The experimental images of both the (2 X 2)(O) and the (root 3 X root 3)R30(O)degrees structures are well reproduced by the simulations. Further CO adsorption caused a second phase transition into a p(2 X 1)(O) structure. The STM simulations strongly support a pure oxygen p(2 X 1) structure, rather than a mixed 0 + CO structure, in contrast to previous experimental work. The CO molecules form the same structures between the O islands that are known from the pure Pd(111)/CO system. At lower temperatures, between 110 and 60 K, a so far unknown (2 X 2) phase was observed. The formation of this structure, and its imaging by the STM, show that it constitutes a mixed p(2 X 2)(O+CO) structure, where the oxygen atoms remain unchanged, and the CO molecules occupy hcp sites between the O atoms.