By carefully mixing Pd metal nanoparticles with CeO2 polycrystalline powder under dry conditions, an unpredicted arrangement of the Pd-O-Ce interface is obtained in which an amorphous shell containing palladium species dissolved in ceria is covering a core of CeO2 particles. The robust contact that is generated at the nanoscale, along with mechanical forces generated during mixing, promotes the redox exchange between Pd and CeO2 and creates highly reactive and stable sites constituted by PdOx embedded into CeO2 surface layers. This specific arrangement outperforms conventional Pd/CeO2 reference catalysts in methane oxidation by lowering light-off temperature by more than 50°C and boosting the reaction rate. The origin of the outstanding activity is traced to the structural properties of the interface, modified at the nanoscale by mechanochemical interaction.