Platinum and palladium are frequently used as catalytic materials, for example for the oxidation of CO. This is one of the most widely studied reactions in the field of surface science. Although seemingly uncomplicated, it remains an active and interesting topic, which is partially explained by the push to conduct experiments on model systems under relevant reaction conditions. Recent developments in the surface-science methodology have allowed obtaining chemical and structural information on the active phase of model catalysts. Tools of the trade include near-ambient-pressure X-ray photoelectron spectroscopy, high-pressure scanning tunneling microscopy, high-pressure surface X-ray diffraction, and high-pressure vibrational spectroscopy. Interpretation is often aided by density functional theory in combination with thermodynamic and kinetic modeling. In this review, results for the catalytic oxidation of CO obtained by these techniques are compared. On several of the Pt and Pd surfaces, new structures develop in excess O2. For Pt, this requires a much larger excess of O2 than for Pd. Most of these structures also develop in pure O2 and are identified as (surface) oxides. A large body of evidence supports the conjecture that these oxides are more reactive than the corresponding O-covered metallic surfaces under similar conditions, although still debated in the literature. An outlook on this developing field, including directions that move away from CO oxidation towards more complex chemistry, concludes this review.