A series of Nb-doped (0–23 wt%) cryptomelane catalyst (Nb-K-OMS-2) was synthesized and thoroughly characterized by XRD, TEM/EDX, XRF, XPS, XAS, UV-Vis, and Raman techniques corroborated by the work function measurements. The obtained catalysts were tested for soot oxidation (Printex U) in model tight and loose contact modes. It was shown that the catalytic properties of the Nb-K-OMS-2 are controlled by the amount of Nb dopant in a strongly non-monotonous way. The introduction of niobium gives rise to the strain in the cryptomelane lattice, accompanied by significant Mn+3/Mn+4 ratio variations and concomitant work function changes. The isotopic exchange experiments revealed that the catalytic activity of the Nb-OMS-2 catalysts in soot combustion proceeds via the pathways, where both the activated suprafacial 18O and the surface 16O2− species participate together in the reaction. The niobium doping level controls the non-monotonous changes of the catalyst work function and the lattice strain, and variations of these parameters correlate well with the observed deSoot activity. To our best knowledge, the role of the lattice strain of the cryptomelane catalysts was documented for the first time in this study.