The total oxidation of toluene was studied over a Co3O4/La-CeO2 catalyst in a Temporal Analysis of Products (TAP) set-up in the temperature range 713 K to 873 K in the presence and absence of dioxygen. It has been demonstrated that the reaction proceeds via a Mars-van Krevelen mechanism. The reaction rate increased 8.4 times if both toluene and dioxygen were present in the feed. The partial reaction order with respect to O2 diminished from 0.9 to 0.6 with an increase in temperature from 763 to 873 K. Adsorbed oxygen species with a lifetime of ∼8 s have been found on a catalyst fully oxidized by dioxygen. Catalysis of isotopically labeled (18)O2/(12)C6H5(13)CH3 results in the formation of products containing (18)O, which indicates that both lattice and adsorbed oxygen are involved in the total oxidation of toluene. The role of adsorbed oxygen is activation of the C-H bond in toluene. The reaction network of the catalytic total oxidation of toluene consists of the following sequence: adsorption of toluene on the catalyst surface; activation of toluene by dehydrogenation with adsorbed oxygen; oxidation of activated toluene mainly by the lattice oxygen and re-oxidation of the reduced catalyst by dioxygen.