In this work novel nickel catalysts based on nickel aluminate deposited on [GRAPHIC] ceria-based supports (CeO2 and Ce0.13Zr0.87O2) were investigated for the partial oxidation of methane. The good catalytic behavior of the CeO2-based sample under moderate (38400 mL of CH4 g(-1) h(-1) and stoichiometric feed) and severe (60000 mL of CH4 g(-1) h(-1), an O/C molar ratio of 0.8, and prolonged time on stream (30 h)) reaction conditions was mainly assigned to the small particle size (about 10 nm) that was achieved after the high temperature reduction of the spinel and its notable redox properties. CeAl O-3 formation was found to have a negative effect on the catalytic performance, which was more pronounced for the Ce-0.13,Zr0.87O2-supported catalyst. This negative impact could be controlled by the introduction of La2O3 since this promoter reacted with alumina to give LaAlO3 instead of CeAlO3 and favored carbon gasification in the vicinity of nickel particles.