In this work a series of palladium doped cobalt spinel catalysts was synthesized via solution combustion synthesis plus incipient wetness impregnation and tested in lean CH4 oxidation. The obtained catalysts were characterized from the structural and surface point of view (XRD, XRF, μRS, BET). The Pd doping level, calculated as PdO, ranged from 0.5 to 5 wt.%. The optimal palladium loading was determined on the basis of catalytic tests in gas mixtures containing from 0.5 to 2 vol.% of CH4. The temperature window for the catalytic activity of the Pd/Co3O4 materials spread from 270 to 550 °C. The optimal Pd loading was found to be 3 wt.%, and it was rationalized in terms of favorable surface Pd dispersion, since above this critical level of 3% an appreciable amount of PdO phase was formed. The reactivity of the optimal 3 wt.% Pd/Co3O4 catalyst from one-shot solution combustion synthesis was evaluated with the aim of optimizing the synthesis procedure.