The structure and chemical composition of Pd nanoparticles exposed to pure CO and mixtures of CO and O(2) at elevated temperatures have been studied in situ by a combination of X-ray Diffraction and X-ray Photoelectron Spectroscopy in pressures ranging from ultra high vacuum to 10 mbar and from room temperature to a few hundred degrees celsius. Our investigation shows that under CO exposure, above a certain temperature, carbon dissolves into the Pd particles forming a carbide phase. Upon exposure to CO and O(2) mixtures, the carbide phase forms and disappears reversibly, switching at the stoichiometric ratio for CO oxidation. This finding opens new scenarios for the understanding of catalytic oxidation of C-based molecules.