Resolving the structure and composition of supported nanoparticles under reaction conditions remains a challenge in heterogeneous catalysis. Advanced configurational sampling methods at the density functional theory level are used to identify stable structures of a Pd₈ cluster on ceria (CeO₂) in the absence and presence of O₂. A Monte Carlo method in the Gibbs ensemble predicts Pd-oxide particles to be stable on CeO₂ during CO oxidation. Computed potential energy diagrams for CO oxidation reaction cycles are used as input for microkinetics simulations. Pd-oxide exhibits a much higher CO oxidation activity than metallic Pd on CeO₂. This work presents for the first time a scaling relation for a CeO₂-supported metal nanoparticle catalyst in CO oxidation: a higher oxidation degree of the Pd cluster weakens CO binding and facilitates the rate-determining CO oxidation step with a ceria O atom. Our approach provides a new strategy to model supported nanoparticle catalysts.