Carnivores tend to exhibit a lack of (or less pronounced) genetic structure at continental scales in both a geographic and temporal sense using various mitochondrial DNA markers on modern and/or ancient specimens. This tends to confound the identification of refugial areas and post-glacial colonization patterns in this group. In this study we used Genotyping-by-Sequencing (GBS) to reconstruct the phylogeographic history of a widespread carnivore, the red fox (Vulpes vulpes), in Europe by investigating broad-scale patterns of genomic variation, differentiation and admixture amongst contemporary populations. Using 15,003 single nucleotide polymorphisms (SNPs) from 524 individuals allowed us to identify the importance of refugial regions for the red fox in terms of endemism (e.g. Iberia) and sources of post-glacial re-expansion (e.g. Carpathians and Balkans) across northern regions of the continent. In addition, we tested multiple post-glacial re-colonization scenarios of previously glaciated regions during the Last Glacial Maximum using an Approximate Bayesian Computation (ABC) approach. We identified the role of ancient and temporary land-bridges in the colonization of Scandinavia and the British Isles, with a natural colonization of Ireland deemed more likely than an ancient human-mediated introduction as has previously been proposed. Using genome-wide data has allowed us to tease apart broad-scale patterns of structure and diversity in a widespread carnivore in Europe that was not always evident from using more limited marker sets.