Oscillations in the Earth’s temperature and the subsequent retreating and advancing of ice-sheets around the polar regions are thought to have played an important role in shaping the distribution and genetic structuring of contemporary high-latitude populations. After the Last Glacial Maximum (LGM), retreating of the ice-sheets would have enabled early colonizers to rapidly occupy suitable niches to the exclusion of other conspecifics, thereby reducing genetic diversity at the leading-edge. Bottlenose dolphins (genus Tursiops) form distinct coastal and pelagic ecotypes, with finer scale genetic structuring observed within each ecotype. We reconstruct the post-glacial colonization of the Northeast Atlantic (NEA) by bottlenose dolphins using habitat modelling and phylogenetics. The AquaMaps model hindcasted suitable habitat for the LGM in the Atlantic lower latitude waters and parts of the Mediterranean Sea. The time-calibrated phylogeny, constructed with 86 complete mitochondrial genomes including 30 generated for this study and created using a multi-species coalescent model, suggests that the expansion to the available coastal habitat in the NEA happened via founder events starting ~15,000 years ago (95% highest posterior density interval: 4,900–26,400). The founders of the two distinct coastal NEA populations comprised as few as two maternal lineages that originated from the pelagic population. The low effective population size and genetic diversity estimated for the shared ancestral coastal population subsequent to divergence from the pelagic source population are consistent with leading-edge expansion. These findings highlight the legacy of the Late Pleistocene glacial cycles on the genetic structuring and diversity of contemporary populations.