Abstract Background Significant effects of recent global climate change have already been observed in a variety of ecosystems, with evidence for shifts in species ranges, but rarely have such consequences been related to the changes in the species genetic pool. The stretch of Atlantic coast between North Africa and North Iberia is ideal for studying the relationship between species distribution and climate change as it includes the distributional limits of a considerable number of both cold- and warm-water species. We compared temporal changes in distribution of the canopy-forming alga Fucus vesiculosus with historical sea surface temperature (SST) patterns to draw links between range shifts and contemporary climate change. Moreover, we genetically characterized with microsatellite markers previously sampled extinct and extant populations in order to estimate resulting cryptic genetic erosion. Results Over the past 30 years, a geographic contraction of the southern range edge of this species has occurred, with a northward latitudinal shift of approximately 1,250 km. Additionally, a more restricted distributional decline was recorded in the Bay of Biscay. Coastal SST warming data over the last three decades revealed a significant increase in temperature along most of the studied coastline, averaging 0.214°C/decade. Importantly, the analysis of existing and extinct population samples clearly distinguished two genetically different groups, a northern and a southern clade. Because of the range contraction, the southern group is currently represented by very few extant populations. This southern edge range shift is thus causing the loss of a distinct component of the species genetic background. Conclusions We reveal a climate-correlated diversity loss below the species level, a process that could render the species more vulnerable to future environmental changes and affect its evolutionary potential. This is a remarkable case of genetic uniqueness of a vanishing cryptic genetic clade (southern clade).