In this work, we investigated the effects of two different synthetic routes, Pechini and microwave-induced combustion method, on the properties of nickel-based catalysts derived from NiO-Ce0.75Zr0.25O2 nanocomposite. Powder samples were characterized by specific surface area (SSA) via BET method, X-ray diffraction (XRD), scanning electron microscopy (SEM) and temperature-programmed reduction (TPR). It was found that the synthesis method has a significant influence on the powder morphology, which may affect the catalytic activity. The nickel-based catalysts were tested for the partial oxidation of methane showing high CH4 conversion, 80% and 81% after the first hour on stream, for the samples prepared by Pechini and combustion method, respectively. These samples also exhibited catalytic stability, keeping CH4 conversion levels about 77% and 80% after ten hours on stream, respectively. We suggest that such good performance is related to the good dispersion and particle size of the metallic nickel over Zr-CeO2 support.