A series of Pd/CeO2 catalysts was prepared by solution combustion synthesis (SCS) using different Pd precursors. The powders were characterized by complementary techniques such as BET surface area measurements, X-Ray diffraction analysis, X-Ray photoelectron spectroscopy, temperature-programmed reduction, temperature-programmed oxidation, and high-resolution TEM. The results obtained evidenced the formation of a Pd-Ce solid solution on all SCS samples. This solid solution is in the form of an ordered supercell structure only in the SCS catalyst prepared from palladium nitrate. This was correlated to the heat of reaction between Pd(NO3)2 and the fuel. The samples were tested for methane catalytic combustion, and the reaction rates on all SCS samples were approximately twice that of the impregnated counterpart, irrespective of the precursor. This was attributed to the presence of the Pd-O-Ce solid solution, which gave rise to strong Pd–ceria interactions.