Combining temperature-programmed reaction measurements, isotopic labeling experiments, and first-principles density functional theory, the dependence of the reaction temperature of catalyzed carbon monoxide oxidation on the oxidation state of Pd13 clusters deposited on MgO surfaces grown on Mo(100) is explored. It is shown that molecular oxygen dissociates easily on the supported Pd13 cluster leading to facile partial oxidation to form Pd13O4 clusters with C4v symmetry. Increasing the oxidation temperature to 370 K, results in non-symmetric 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 non-symmetric Pd13O6 clusters show lower temperature catalyzed CO combustion, already starting at cryogenic temperature.