The need for active and stable oxidation catalysts is driven by the demands in production of valuable chemicals, remediation of hydrocarbon pollutants and energy sustainability. Traditional approaches focus on oxygen-activating oxides as support which provides the oxygen activation at the catalyst-support peripheral interface. Here we report a new approach to oxidation catalysts for total oxidation of hydrocarbons (e.g., propane) by surface oxygenation of platinum (Pt)-alloyed multicomponent nanoparticles (e.g., platinum-nickel cobalt (Pt-NiCo)). The in-situ/operando time-resolved studies, including high-energy synchrotron X-ray diffraction and diffuse reflectance infrared Fourier transform spectroscopy, demonstrate the formation of oxygenated Pt-NiOCoO surface layer and disordered ternary alloy core. The results reveal largely-irregular oscillatory kinetics associated with the dynamic lattice expansion/shrinking, ordering/disordering, and formation of surface-oxygenated sites and intermediates. The catalytic synergy is responsible for reduction of the oxidation temperature by ~100 °C and the high stability under 800 °C hydrothermal aging in comparison with Pt, and may represent a paradigm shift in the design of self-supported catalysts.