Previous molecular studies of the wide-ranging Eurasian lynx Lynx lynx focused mainly on its northern Palearctic populations, with the consequence that the reconstruction of this species’ evolutionary history did not include genetic variation present in its southern Palearctic distribution. We sampled a previously not considered Asian subspecies (L. l. dinniki), added published data from another Asian subspecies (L. l. isabellinus), and reassessed the Eurasian lynx mtDNA phylogeny along with previously published data from northern Palearctic populations. Our mitogenome-based analyses revealed the existence of three major clades (A: Central Asia, B: SE Europe/SW Asia, C: Europe and Northern Asia) and at least five lineages, with diversification in Lynx lynx commencing at least 28kyr earlier than hitherto estimated. The subspecies L. l. isabellinus harbors the most basal matriline, consistent with the origin of Lynx lynx in this subspecies’ current range. L. l. dinniki harbors the second most basal matriline, which is related to, and may be the source of, the mtDNA diversity of the critically endangered Balkan lynx L. l. balcanicus. Our results suggest that the Anatolian peninsula was a glacial refugium for Eurasian lynx, with previously unconsidered implications for the colonization of Europe by this species.