The isotopic exchange reaction on ZrO2 and yttrium-stabilized ZrO2 (YSZ) during catalytic partial oxidation of methane to synthesis gas (CPOM) was studied with transient pulse experiments. The results reveal, surprisingly, that CPOM over both oxides proceeds via a Mars¿van Krevelen mechanism. Despite the presence of adsorbed oxygen species, as confirmed by isotopic exchange experiments under reaction conditions, methane is selectively oxidized by lattice oxygen ions on the surfaces of YSZ and ZrO2. At 900 °C, about 8 and 14% of lattice oxygen in the outermost surface layer of ZrO2 and YSZ, respectively, can be extracted by methane. Extraction of lattice oxygen results in the formation of surface oxygen vacancies. However, the routes for replenishing oxygen differ for the two oxides. For ZrO2, the extracted lattice oxygen ions are replenished by direct activation of molecular oxygen at the site of the surface vacancy. The presence of a high concentration of surface oxygen vacancies on YSZ, generated by doping of ZrO2 with Y2O3, permits fast activation of oxygen molecules and fast lattice diffusion of oxygen. The two effects together lead to a rapid replenishment of the surface lattice oxygen extracted by methane. The proposed mechanism explains both the comparatively high activity of YSZ in CPOM and the observation that, in contrast to ZrO2, lattice oxygen is found exclusively in oxidation products of methane over YSZ during pulse experiments.