Combining temperature-programmed reaction measurements, isotopic labeling experiments, and first-principles spin density functional theory, the dependence of the reaction temperature of catalyzed carbon monoxide oxidation on the oxidation state of Pd(13) clusters deposited on MgO surfaces grown on Mo(100) is explored. It is shown that molecular oxygen dissociates easily on the supported Pd(13) cluster, leading to facile partial oxidation to form Pd(13)O(4) clusters with C(4v) symmetry. Increasing the oxidation temperature to 370 K results in nonsymmetric Pd(13)O(6) clusters. The higher symmetry, partially oxidized cluster is characterized by a relatively high activation energy for catalyzed combustion of the first CO molecule via a reaction of an adsorbed CO molecule with one of the oxygen atoms of the Pd(13)O(4) cluster. Subsequent reactions on the resulting lower-symmetry Pd(13)O(x) (x < 4) clusters entail lower activation energies. The nonsymmetric Pd(13)O(6) clusters show lower temperature-catalyzed CO combustion, already starting at cryogenic temperature.