Density functional calculations were performed in order to investigate CO oxidation on two of the most stable bulk PdO surfaces. The most stable PdO(100) surface, with oxygen excess, is inert against CO adsorption, whereas strong adsorption on the stoichiometric PdO(101) surface leads to favorable oxidation via the Langmuir–Hinshelwood mechanism. The reaction with a surface oxygen atom has an activation energy of 0.66 eV, which is comparable to the lowest activation energies observed on metallic surfaces. However, the reaction rate may be limited by the coverage of molecular oxygen. Actually, the reaction with the site blocking molecular oxygen is slightly more favorable, enabling also possible formation of carbonate surface species at low temperatures. The extreme activity of strongly bonded surface oxygen atoms is more greatly emphasized on the PdO(100)–O surface. The direct reaction without adsorption, following the Eley–Rideal mechanism and taking advantage of the reaction tunnel provided by the adjacent palladium atom, has an activation energy of only 0.24 eV. The reaction mechanism and activation energy for the palladium activated CO oxidation on the most stable PdO(100)–O surface are in good agreement with experimental observations.