The Anatolian Peninsula, comprising most of modern Turkey, is situated at the junction of Europe, the Middle East and Asia. Together with its complex geomorphological and climatic history, this has given rise to a rich fauna and flora, which exhibits a wide range of historical biogeographical patterns. The stone marten (Martes foina) is a small carnivore that is found across the temperate Palaearctic region including Anatolia, where it is often associated with habitats modified by humans, but few genetic data exist for this species. We sequenced a 1840-bp region of the mitochondrial genome from 97 martens sampled across the peninsula and intron 7 of the nuclear 13-fibrinogen gene from 53 of these. Two mitochondrial lineages were recovered, with overlapping eastern and western distributions, but there was no geographical structure for the autosomal marker. Coalescent analyses indicated that both of the lineages originated during the Last Glacial Maximum, one of them within an eastern Anatolian refugium and the other in a western Anatolian or Balkan refugium. The western lineage colonized most of Europe in the Holocene, while the eastern lineage may be endemic to Anatolia, from where it colonized the Iberian Peninsula via human translocation. The presence of at least one refugial stone marten population highlights the importance of Anatolia to the preservation of genetic variation and biodiversity.