Although the grey seal Halichoerus grypus is one of the most familiar and intensively studied of all pinniped species, its global population structure remains to be elucidated. Little is also known about how the species as a whole may have historically responded to climate-driven changes in habitat availability and anthropogenic exploitation. We therefore analysed samples from over 1500 individuals collected from 22 colonies spanning the Western and Eastern Atlantic and the Baltic Sea regions, represented by 350bp of the mitochondrial hypervariable region and up to nine microsatellites. Strong population structure was observed at both types of marker, and highly asymmetrical patterns of gene flow were also inferred, with the Orkney islands being identified as a source of emigrants to other areas in the Eastern Atlantic. The Baltic and Eastern Atlantic regions were estimated to have diverged a little over 10,000 years ago, consistent with the last proposed isolation of the Baltic Sea. Approximate Bayesian computation also identified genetic signals consistent with postglacial population expansion across much of the species range, suggesting that grey seals are highly responsive to changes in habitat availability.