A major aim of evolutionary biology is to understand why patterns of genomic variation vary among populations and species. Large-scale genomic studies of widespread species are useful for studying how the environment and demographic history shape patterns of genomic divergence, and with the continually decreasing cost of sequencing, such studies are now becoming feasible. Here, we carry out one of the most comprehensive surveys of genomic variation in a wild vertebrate to date; the great tit (Parus major) HapMap project. We screened ca 500,000 SNP markers across 647 individuals from 28 populations, spanning almost the entire geographic range of the European great tit subspecies. We found that genome-wide variation was consistent with a recent colonisation across Europe from a single refugium in the Balkans and/or Turkey, with bottlenecks and reduced genetic diversity in island populations. Differentiation across the genome was highly heterogeneous, with clear 'islands of differentiation' even among populations which are ostensibly panmictic. These islands of differentiation were consistently found in regions of low recombination, suggesting that background selection can rapidly promote population differentiation among even the most recently colonised populations. We also detected outlier regions that were unique to peripheral great tit populations, most likely as a result of recent directional selection at the range edges of this species. These 'unique' outlier regions contained candidate genes for morphology, stress response and colouration, supporting previous research in this species, and providing avenues for future investigation. Our study suggests that comprehensive screens of genomic variation in wild organisms can provide unique insights into evolution.