Phylogeography has provided a new approach to the analysis of the postglacial history of a wide range of taxa but, to date, little is known about the effect of glacial periods on the marine biota of Europe. We have utilized a combination of nuclear, plastid and mitochondrial genetic markers to study the biogeographic history of the red seaweed Palmaria palmata in the North Atlantic. Analysis of the nuclear rDNA operon (ITS1-5.8S-ITS2), the plastid 16S-trnI-trnA-23S-5S, rbcL-rbcS and rpl12-rps31-rpl9 regions and the mitochondrial cox2-3 spacer has revealed the existence of a previously unidentified marine refugium in the English Channel, along with possible secondary refugia off the southwest coast of Ireland and in northeast North America and/or Iceland. Coalescent and mismatch analyses date the expansion of European populations from approximately 128,000 BP and suggest a continued period of exponential growth since then. Consequently, we postulate that the penultimate (Saale) glacial maximum was the main event in shaping the biogeographic history of European P. palmata populations which persisted throughout the last (Weichselian) glacial maximum (c. 20,000 BP) in the Hurd Deep, an enigmatic trench in the English Channel.