To improve the catalytic performance of an active layered double hydroxide (LDH)-derived CuCeMgAlO mixed oxide catalyst in the total oxidation of methane, it was promoted with different transition-metal cations. Thus, two series of multicationic mixed oxides were prepared by the thermal decomposition at 750 °C of their corresponding LDH precursors synthesized by coprecipitation at constant pH of 10 under ambient atmosphere. The first series of catalysts consisted of four M(3)CuCeMgAlO mixed oxides containing 3 at.% M (M = Mn, Fe, Co, Ni), 15 at.% Cu, 10 at.% Ce (at.% with respect to cations), and with Mg/Al atomic ratio fixed to 3. The second series consisted of four Co(x)CuCeMgAlO mixed oxides with x = 1, 3, 6, and 9 at.% Co, while keeping constant the Cu and Ce contents and the Mg/Al atomic ratio. All the mixed oxides were characterized by powder X-ray diffraction (XRD), transmission electron microscopy (TEM), scanning electron microscopy (SEM) coupled with X-ray energy dispersion analysis (EDX), X-ray photoelectron spectroscopy (XPS), nitrogen adsorption-desorption at −196 °C, temperature-programmed reduction under hydrogen (H2-TPR), and diffuse reflectance UV-VIS spectroscopy (DR UV-VIS), while thermogravimetric and differential thermal analyses (TG-DTG-DTA) together with XRD were used for the LDH precursors. The catalysts were evaluated in the total oxidation of methane, a test reaction for volatile organic compounds (VOC) abatement. Their catalytic performance was explained in correlation with their physicochemical properties and was compared with that of a reference Pd/Al2O3 catalyst. Among the mixed oxides studied, Co(3)CuCeMgAlO was found to be the most active catalyst, with a temperature corresponding to 50% methane conversion (T50) of 438 °C, which was only 19 °C higher than that of a reference Pd/Al2O3 catalyst. On the other hand, this T50 value was ca. 25 °C lower than that observed for the unpromoted CuCeMgAlO system, accounting for the improved performance of the Co-promoted catalyst, which also showed a good stability on stream.