Aim: To infer cold-water corals' (CWC) post-glacial phylogeography and assess the role of Mediterranean Sea glacial refugia as origins for the recolonization of the northeastern Atlantic Ocean.Location: Northeastern Atlantic Ocean and Mediterranean Sea.Taxon: Lophelia pertusa, Madrepora oculata.Methods: We sampled CWC using remotely operated vehicles and one sediment core for coral and sediment dating. We characterized spatial genetic patterns (microsatellites and a nuclear gene fragment) using networks, clustering and measures of genetic differentiation.Results: Inferences from microsatellite and sequence data were congruent, and showed a contrast between the two CWC species. Populations of L. pertusa present a dominant pioneer haplotype, local haplotype radiations and a majority of endemic variation in lower latitudes. Madrepora oculata populations are differentiated across the northeastern Atlantic and genetic lineages are poorly admixed even among neighbouring sites.Conclusions: Our study shows contrasting post-glacial colonization pathways for two key habitat-forming species in the deep sea. The CWC L. pertusa has likely undertaken a long-range (post-glacial) recolonization of the northeastern Atlantic directly from refugia located along southern Europe (Mediterranean Sea or Gulf of Cadiz). In contrast, the stronger genetic differentiation of M. oculata populations mirrors the effects of long-term isolation in multiple refugia. We suggest that the distinct and genetically divergent, refugial populations initiated the post-glacial recolonization of the northeastern Atlantic margins, leading to a secondary contact in the northern range and reaching higher latitudes much later, in the late Holocene. This study highlights the need to disentangle the influences of present-day dispersal and evolutionary processes on the distribution of genetic polymorphisms, to unravel the influence of past and future environmental changes on the connectivity of cosmopolitan deep-sea ecosystems associated with CWC.