In this study, Ni, Co and Ni−Co catalysts supported on binary oxide ZrO2−Al2O3 were synthesized by sol-gel method and characterized by means of various analytical techniques such as XRD, BET, TPR, TPD, TGA, SEM, and TEM. This catalytic system was then tested for syngas respective H2 production via partial oxidation of methane at 700 °C and 800 °C. The influence of calcination temperatures was studied and their impact on catalytic activity and stability was evaluated. It was observed that increasing the calcination temperature from 550 °C to 800 °C and addition of ZrO2 to Al2O3 enhances Ni metal-support interaction. This increases the catalytic activity and sintering resistance. Furthermore, ZrO2 provides higher oxygen storage capacity and stronger Lewis basicity which contributed to coke suppression, eventually leading to a more stable catalyst. It was also observed that, contrary to bimetallic catalysts, monometallic catalysts exhibit higher activity with higher calcination temperature. At the same time, Co and Ni−Co-based catalysts exhibit higher activity than Ni-based catalysts which was not expected. The Co-based catalyst calcined at 800 °C demonstrated excellent stability over 24 h on stream. In general, all catalysts demonstrated high CH4 conversion and exceptionally high selectivity to H2 (~98%) at 700 °C.