Red deer (Cervus elaphus) have played a key role in human societies throughout history, with important cultural significance and as a source of food and materials. This relationship can be traced back to the earliest human cultures and continues to the present day. Humans are thought to be responsible for the movement of a considerable number of deer throughout history, although the majority of these movements are poorly described or understood. Studying such translocations allows us to better understand ancient human–wildlife interactions, and in the case of island colonizations, informs us about ancient human maritime practices. This study uses DNA sequences to characterise red deer genetic diversity across the Scottish islands (Inner and Outer Hebrides and Orkney) and mainland using ancient deer samples, and attempts to infer historical colonization events. We show that deer from the Outer Hebrides and Orkney are unlikely to have originated from mainland Scotland, implying that humans introduced red deer from a greater distance. Our results are also inconsistent with an origin from Ireland or Norway, suggesting long-distance maritime travel by Neolithic people to the outer Scottish Isles from an unknown source. Common haplotypes and low genetic differentiation between the Outer Hebrides and Orkney imply common ancestry and/or gene flow across these islands. Close genetic proximity between the Inner Hebrides and Ireland, however, corroborates previous studies identifying mainland Britain as a source for red deer introductions into Ireland. This study provides important information on the processes that led to the current distribution of the largest surviving indigenous land mammal in the British Isles.