Oxide-supported transition-metal clusters and nanoparticles have attracted significant attention owing to their important role as components of model catalysts(1-6), sensors(7), solar cells(8) and magnetic recording devices(9). For small clusters, functionality and structure are closely interrelated. However, knowledge of the structure of the bare cluster is insufficient as the interaction with the chemical environment might cause drastic structural changes. Here we show by ab initio simulations based on the density functional theory that the reaction with molecular oxygen transforms small, non-crystalline, magnesia-supported Pd-clusters to crystalline PdxOy nano-oxide clusters that are in epitaxy with the underlying support. Restructuring of the Pd backbone is controlled by the electrostatic interaction with magnesia leading to a strong reduction of the O-2 dissociation barrier. The supported PdxOy clusters are likely to serve as Mars-van Krevelen(10) oxygen reservoirs in catalytic oxidation reactions as observed for PdO overlayers(11) and demonstrated here for the oxidation of CO molecules.