How species respond to an increased availability of habitat, for example at the end of the last glaciation, has been well established. In contrast, little is known about the opposite process, when the amount of habitat decreases. The hypothesis of habitat tracking predicts that species should be able to track both increases and decreases in habitat availability. The alternative hypothesis is that populations outside refugia become extinct during periods of unsuitable climate. To test these hypotheses, we used ancient DNA techniques to examine genetic variation in the arctic fox (Alopex lagopus) through an expansion/contraction cycle. The results show that the arctic fox in midlatitude Europe became extinct at the end of the Pleistocene and did not track the habitat when it shifted to the north. Instead, a high genetic similarity between the extant populations in Scandinavia and Siberia suggests an eastern origin for the Scandinavian population at the end of the last glaciation. These results provide new insights into how species respond to climate change, since they suggest that populations are unable to track decreases in habitat avaliability. This implies that arctic species may be particularly vulnerable to increases in global temperatures.