Manganese oxides attract considerable attention as redox catalysts for abatement of environmental pollutants due to their relatively high activity and low costs contrary to noble metal catalysts. The present work is focused on the effect of cryptomelane-type MnO2 catalyst modification with Fe3+, Ce3+/Ce4+, Sn4+ on their phase composition, structural peculiarities, and catalytic activity in CO oxidation. The samples are investigated by XRD, Raman spectroscopy, XPS, XRF, and comprehensive HRTEM, with their catalytic activity being studied under the model dry conditions and simulated real exhaust conditions comprising CO, O2, and water balanced by inert. The Mn4+ substitution in the cryptomelane structure by Men+ is revealed to result in its monoclinic distortion, with the Sn- and Fe-doped cryptomelane-type MnO2 formation being accompanied by the formation of SnO2 and Fe1−xMnxO3/Fe1+xMn2−xO4, respectively. For Ce-doped samples, the K+ presence in the cryptomelane tunnels is essential to stabilize the cryptomelane structure and nanorod morphology. The cryptomelane structure stabilized by only Cen+ cations is collapsed during the sample calcination to form Mn2−xCexO3 and Mn3−xCexO4, while high Ce content does not favor the formation of the cryptomelane-type MnO2. The composites based on the Me-doped cryptomelane-type α- MnO2, especially those doped with Ce, are shown to be promising candidates to develop effective oxidebased catalysts for CO oxidation.