Due to its warming potential over 20 times higher than that of CO2, methane is classified as one of the most dangerous pollutants. Removal of methane emitted particularly from low calorific sources, such as coal mine ventilation air streams or dumping grounds, falls thus in line with the most important challenges of environmental catalysis. Main goal of this work was to verify the efficiency and to understand the catalytic behavior of a series of coprecipitated MnOx–CeO2 mixed oxide samples, containing nominally 30–80 mol% of MnO2. A plethora of structural (XRD, RS), textural (BET), and spectroscopic (EPR, XPS, and RS) methods have been applied for sample characterization. Catalytic activity has been determined by TPSR in the temperature range from 100 to 700 C. It was shown that catalytic activity of the investigated MnOx–CeO2 samples is strongly related to their structural heterogeneity and reducibility of various manganese centers coexisting within the surface MnOx clusters interacting with nanocrystalline CeO2.