Temperate terrestrial species in Europe were hypothesized to have been restricted to southern peninsular refugia (Iberia, Italy, Balkans) during the height of the last glacial period. However, recent analyses of fossil evidence indicate that some temperate species existed outside these areas during the last glacial maximum (LGM). Red foxes (Vulpes vulpes) in particular, could have been distributed across the southern half of the continent, potentially forming one continuous population. To investigate these hypotheses, we used 21 nuclear microsatellite loci and two fragments (768 bp) of mitochondrial DNA to characterize the population structure among a continent-wide sample of 288 European red foxes. We tested whether European red foxes clustered into discrete populations corresponding to the hypothetical peninsular refugia. Additionally, we sought to determine if distinct northern populations were formed after post-glacial recolonization. Our results indicated that only the foxes of Iberia appeared to have remained distinct over a considerable period of time (32–104 kya). Spanish red foxes formed their own genotypic cluster; all mtDNA haplotypes were endemic and closely related, and together both the mitochondrial and nuclear datasets indicated this population contributed little to postglacial recolonization of Northern Europe. In contrast, red foxes from Italy and the Balkans contributed significantly to, or were part of, a wider, admixed population stretching across mid-latitude Europe. In Northern Europe, we identified a Scandinavian population that had an ancestral relationship with red foxes to the south, and a more recent relationship with those to the east, in Russia. We also resolved two distinct populations on the islands of Ireland and Britain that had been separated from one another, and from those on the continent, since the late Pleistocene/mid Holocene (∼4–24 kya).