The largest population of red deer (Cervus elaphus) in Europe is found in Scotland. However, human impacts through hunting and introduction of foreign deer stock have disturbed the population's genetics to an unknown extent. In this study, we analysed mitochondrial control region sequences of 625 individuals to assess signatures of human and natural historical influence on the genetic diversity and population structure of red deer in the Scottish Highlands. Genetic diversity was high with 74 haplotypes found in our study area (115 x 87 km). Phylogenetic analyses revealed that none of the individuals had introgressed mtDNA from foreign species or subspecies of deer and only suggested a very few localized red deer translocations among British localities. A haplotype network and population analyses indicated significant genetic structure (Phi(ST)=0.3452, F(ST)=0.2478), largely concordant with the geographical location of the populations. Mismatch distribution analysis and neutrality tests indicated a significant population expansion for one of the main haplogroups found in the study area, approximately dated c. 8200 or 16 400 years ago when applying a fast or slow mutation rate, respectively. Contrary to general belief, our results strongly suggest that native Scottish red deer mtDNA haplotypes have persisted in the Scottish Highlands and that the population retains a largely natural haplotype diversity and structure in our study area.