Climate warming at the end of the last glacial period had profound effects on the distribution of cold-adapted species. As their range shifted towards northern latitudes, they were able to colonise previously glaciated areas, including remote Arctic islands. However, there is still uncertainty about the routes and timing of colonisation. At the end of the last ice age, reindeer/caribou (Rangifer tarandus) expanded to the Holarctic region and colonised the archipelagos of Svalbard and Franz Josef Land. Earlier studies have proposed two possible colonisation routes, either from the Eurasian mainland or from Canada via Greenland. Here, we used 174 ancient, historical and modern mitogenomes to reconstruct the phylogeny of reindeer across its whole range and to infer the colonisation route of the Arctic islands. Our data shows a close affinity among Svalbard, Franz Josef Land and Novaya Zemlya reindeer. We also found tentative evidence for positive selection in the mitochondrial gene ND4, which is possibly associated with increased heat production. Our results thus support a colonisation of the Eurasian Arctic archipelagos from the Eurasian mainland and provide some insights into the evolutionary history and adaptation of the species to its High Arctic habitat.