We present the first structure determination by surface x-ray diffraction during the restructuring of a model catalyst under reaction conditions, i.e., at high pressure and high temperature, and correlate the restructuring with a change in catalytic activity. We have analyzed the Pt(110) surface during CO oxidation at pressures up to 0.5 bar and temperatures up to 625 K. Depending on the pressure ratio, we find three well-defined structures: namely, (i) the bulk-terminated Pt(110) surface, (ii) a thin, commensurate oxide, and (iii) a thin, incommensurate oxide. The commensurate oxide only appears under reaction conditions, i.e., when both and CO are present and at sufficiently high temperatures. Density functional theory calculations indicate that the commensurate oxide is stabilized by carbonate ions (CO3(2-)). Both oxides have a substantially higher catalytic activity than the bulk-terminated Pt surface.