The present distribution of many species is a result of climatic changes during the Pleistocene and human activity. The impact of climate has been accompanied by restrictions of populations into refugia during glacial periods, and subsequent expansions during more favourable conditions, whereas human influence has been associated with hunting practices and translocations. One mammalian species that has been subject to such transformations is the red deer, Cervus elaphus, but the exact nature of these changes has been difficult to determine using only modern DNA. In this study, we obtained new cytochrome b sequences from subfossil remains of deer found in the Crimean Peninsula. A comparison of these sequences with the available recent and ancient sequences allowed to us to reconstruct phylogeographic relationships between Cervus lineages and to determine their potential migration routes at both local and Eurasian scales. Our analyses showed that the Crimean Peninsula was not a glacial refugium for red deer, but rather that red deer colonized Crimea in three independent waves from both Western and Eastern red deer populations. The immigrations were related to local extinctions and replacements of native populations.