The support effect on the catalytic properties of palladium particles has been investigated in the reduction of nitrites by hydrogen at 20 °C in batch conditions. The support material was composed of ceria-zirconia mixed oxide stabilized in the tetragonal structure according to an Evaporation Induced Self-Assembly method. In comparison, a co-precipitation method leads to inhomogeneity in composition related to the partial segregation of the cubic fluorite structure of CeO2. Further textural properties obtained for the two synthesis routes differ as well as changes in the reducibility. Surface analysis demonstrated a more extensive surface reduction of Ce4+ to Ce3+ on the series prepared by coprecipitation correlated to a greater stabilization of metallic Pd particles. However, the best catalytic performances were obtained on low loaded Pd samples supported on the ceria-zirconia support prepared by the Evaporation Induced Self-Assembly method which emphasizes the fact that catalytic properties cannot be simply explained by the stabilization of zero valent precious metal at the vicinity of anionic vacancies. Further calculations of TOF and interfacial rates were achieved and compared to the selectivity behavior suggesting that the localization of Pd in contact with the tetragonal or cubic structure of the solid solution and CeO2 could play a key role in determining the catalytic properties.