Recent climate change has triggered profound reorganization in northeast Atlantic ecosystems, with substantial impact on the distribution of marine assemblages from plankton to fishes. However, assessing the repercussions on apex marine predators remains a challenging issue, especially for pelagic species. In this study, we use Bayesian coalescent modelling of microsatellite variation to track the population demographic history of one of the smallest temperate cetaceans, the harbour porpoise (Phocoena phocoena) in European waters. Combining genetic inferences with palaeo-oceanographic and historical records provides strong evidence that populations of harbour porpoises have responded markedly to the recent climate-driven reorganization in the eastern North Atlantic food web. This response includes the isolation of porpoises in Iberian waters from those further north only approximately 300 years ago with a predominant northward migration, contemporaneous with the warming trend underway since the 'Little Ice Age' period and with the ongoing retreat of cold-water fishes from the Bay of Biscay. The extinction or exodus of harbour porpoises from the Mediterranean Sea (leaving an isolated relict population in the Black Sea) has lacked a coherent explanation. The present results suggest that the fragmentation of harbour distribution range in the Mediterranean Sea was triggered during the warm 'Mid-Holocene Optimum' period (approx. 5000 years ago), by the end of the post-glacial nutrient-rich 'Sapropel' conditions that prevailed before that time.