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 Pd13O4 clusters with C-4 nu symmetry. Increasing the oxidation temperature to 370 K results in nonsymmetric Pd13O6 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 Pd13O4 cluster. Subsequent reactions on the resulting lower-symmetry Pd13Ox (x < 4) clusters entail lower activation energies. The nonsymmetric Pd13O6 clusters show lower temperature-catalyzed CO combustion, already starting at cryogenic temperature.