The oxidation of CO on single Pd atoms anchored to MgO(100) surface oxygen vacancies is studied with temperature-programmed-reaction mass spectrometry and infrared spectroscopy. In one-heating-cycle experiments, CO(2), formed from O(2) and CO preadsorbed at 90 K, is detected at 260 and 500 K. Ab-initio simulations suggest two reaction routes, with Pd(CO)(2)O(2) and PdCO(3)CO found as precursors for the low and high temperature channels, respectively. Both reactions result in annealing of the vacancy and induce migration and coalescence of the remaining Pd-CO to form larger clusters.