The narrow-headed vole, collared lemming and common vole were the most abundant small mammal species across the Eurasian Late Pleistocene steppe-tundra environment. Previous ancient DNA studies of the collared lemming and common vole have revealed dynamic population histories shaped by climatic fluctuations. To investigate the extent to which species with similar adaptations share common evolutionary histories, we generated a dataset comprised the mitochondrial genomes of 139 ancient and 6 modern narrow-headed voles from several sites across Europe and northwestern Asia covering approximately the last 100 thousand years (kyr). We inferred Bayesian time-aware phylogenies using 11 radiocarbon-dated samples to calibrate the molecular clock. Divergence of the main mtDNA lineages across the three species occurred during marine isotope stages (MIS) 7 and MIS 5, suggesting a common response of species adapted to open habitat during interglacials. We identified several time-structured mtDNA lineages in European narrow-headed vole, suggesting lineage turnover. The timing of some of these turnovers was synchronous across the three species, allowing us to identify the main drivers of the Late Pleistocene dynamics of steppe- and cold-adapted species.