The present study reports an improved design for Pd/Ce-Pr catalysts. Pd-impregnated nanostructured ceria-praseodymia catalysts with different compositions were comprehensively characterized and tested for dry and wet methane oxidation. The strong PdO-PrO_x interactions, detected via XRD, TPR/TPO, Raman and HRTEM analyses, retain Pd mainly in its oxidized form in the materials with high praseodymium content, thus resulting in a lower activity. Conversely, the introduction of a limited amount of Pr in ceria allows to obtain a more active catalyst (2% of Pd supported on a mixed oxide with 10% of Pr) than the typical Pd/CeO₂ systems. Hence, the simultaneous presence of Pd in its reduced and oxidized forms results to be a key factor for high activity. Additionally, the higher hydrophobicity of this sample, investigated through NMR and in situ FTIR, markedly reduces the H₂O inhibition effect typical of Pd-based materials, paving the way for using this system in real applications.