In light of current debates on global climate change it has become important to know more on how large, roaming species have responded to environmental change in the past. Using the highly variable mitochondrial control region, we revisit theories of Rangifer colonization and propose that the High Arctic archipelagos of Svalbard, Franz Josef Land, and Novaia Zemlia were colonized by reindeer from the Eurasian mainland after the last glacial maximum. Comparing mtDNA control region sequences from the three Arctic archipelagos showed a strong genetic connection between the populations, supporting a common origin in the past. A genetic connection between the three archipelagos and two Russian mainland populations was also found, suggesting colonization of the Eurasian high Arctic archipelagos from the Eurasian mainland. The age of the Franz Josef Land material (>2000 years before present) implies that Arctic indigenous reindeer colonized the Eurasian Arctic archipelagos through natural dispersal, before humans approached this region.