The palladium oxide cluster Pd6O4+ is formed as the sole product upon reaction of a bare palladium cluster Pd-6(+) with molecular oxygen in an octopole ion trap under multicollision conditions. This oxide cluster is found to be resistant to further oxidation over a large temperature range, and further O-2 molecules merely physisorb on it at cryogenic temperatures. The particular stability of Pd6O4+ is confirmed by the observation that the reaction of Pd-7(+) with O-2 leads to fragmentation resulting in the formation of Pd6O4+. However, in an oxygen-rich O-2/CO mixture, Pd6O4+ is identified as the catalytically active species that effectively facilitates the low-temperature oxidation of CO. Gas-phase reaction kinetics measurements in conjunction with first-principles calculations provide detailed molecular level insight into the nano-oxide cluster chemistry and are able to reveal the full catalytic combustion reaction cycle.