According to the IPCC, the global average temperature is likely to increase by 1.4-5.8 °C over the period from 1990 to 2100. In Polar regions, the magnitude of such climatic changes is even larger than in temperate and tropical biomes. This amplified response is particularly worrisome given that the so-far moderate warming is already impacting Arctic ecosystems. Predicting species responses to rapid warming in the near future can be informed by investigating past responses, as, like the rest of the planet, the Arctic experienced recurrent cycles of temperature increase and decrease (glacial-interglacial changes) in the past. In this study, we compare the response of two important prey species of the Arctic ecosystem, the collared lemming and the narrow-skulled vole, to Late Quaternary climate change. Using ancient DNA and Ecological Niche Modeling (ENM), we show that the two species, which occupy similar, but not identical ecological niches, show markedly different responses to climatic and environmental changes within broadly similar habitats. We empirically demonstrate, utilizing coalescent model-testing approaches, that collared lemming populations decreased substantially after the Last Glacial Maximum; a result consistent with distributional loss over the same period based on ENM results. Given this strong association, we projected the current niche onto future climate conditions based on IPCC 4.0 scenarios, and forecast accelerating loss of habitat along southern range boundaries with likely associated demographic consequences. Narrow-skulled vole distribution and demography, by contrast, was only moderately impacted by past climatic changes, but predicted future changes may begin to affect their current western range boundaries. Our work, founded on multiple lines of evidence suggests a future of rapidly geographically shifting Arctic small mammal prey communities, some of whom are on the edge of existence, and whose fate may have ramifications for the whole Arctic food web and ecosystem.