Doping CeO 2 with Pd atoms has been associated with catalytic CO oxidation, but current surface models do not allow CO adsorption. Here, we report a new structure of Pd-doped CeO 2(111), in which Pd adopts a square planar configuration instead of the previously assumed octahedral configuration. Oxygen removal from this doped structure is favorable. The resulting defective Pd-doped CeO 2 surface is active for CO oxidation and is also able to cleave the first C-H bond in methane. We show how the moderate CO adsorption energy and dynamic features of the Pd atom upon CO adsorption and CO oxidation contribute to a low-barrier catalytic cycle for CO oxidation. These structures, which are also observed for Ni and Pt, can lead to a more open coordination environment around the doped-transition-metal center. These thermally stable structures are relevant to the development of single-atom catalysts.