The complete oxidation of methane into water and carbon dioxide on the (I 11) surface of ceria is considered within a DFT + U framework in order to gain insight into the coke-free operation of solid oxide fuel cells with ceria-containing anodes. Preferred adsorption sites and energies are determined for CH, (x = 0,..., 3), H, and CO, together with transition states and kinetic barriers along the complete pathway from CH4 to H2O and CO2. The results presented are in excellent agreement with existing theoretical and experimental work suggesting that ceria is more easily reduced by CO than by H-2 and offer an explanation for the apparently inconsistent observations of carbon coke formation in Ni-ceria anodes and the stable, coke-free oxidation of methane in Cu-ceria anodes.