Ceria-supported Pd is one of the main components in modern three-way catalysts in automotive applications to facilite CO oxidation. The exact form in which Pd displays its high activity remains not well understood. We present a DFT+U study of CO oxidation for single Pd atoms located on or in the ceria surface as well as a Pdn nanorod model on the CeO2(110) surface. The oxidation of Pd to the 2+ state by ceria weakens the Pd-CO bond for the single Pd models and, in this way, facilitates CO2 formation. After CO oxidation by O of the ceria surface, Pd relocates to a position below the surface for the Pd-doped model; in this state, CO adsorption is not possible anymore. With Pd on the surface, O2 will adsorb and dissociate leading to PdO, which can be easily reduced to Pd. The reactivity of the Pd nanorod is low because of the strong bonds of the metallic Pd phase with CO and the O atom derived from O2 dissociation. These findings show that highly dispersed Pd is the most likely candidate for CO oxidation in the Pd-CeO2 system.