Freshwater biodiversity has declined dramatically in Europe in recent decades. Because of massive habitat pollution and morphological degradation of water bodies, many once widespread species persist in small fractions of their original range. These range contractions are generally believed to be accompanied by loss of intraspecific genetic diversity, due to the reduction of effective population sizes and the extinction of regional genetic lineages. We aimed to assess the loss of genetic diversity and its significance for future potential reintroduction of the long-tailed mayfly Palingenia longicauda (Olivier), which experienced approximately 98% range loss during the past century. Analysis of 936 bp of mitochondrial DNA of 245 extant specimens across the current range revealed a surprisingly large number of haplotypes (87), and a high level of haplotype diversity (Hd = 0.875). In contrast, historic specimens (6) from the lost range (Rhine catchment) were not differentiated from the extant Rába population (F(ST) = 0.02, p = 0.61), despite considerable geographic distance separating the two rivers. These observations can be explained by an overlap of the current with the historic (Pleistocene) refugia of the species. Most likely, the massive recent range loss mainly affected the range which was occupied by rapid post-glacial dispersal. We conclude that massive range losses do not necessarily coincide with genetic impoverishment and that a species' history must be considered when estimating loss of genetic diversity. The assessment of spatial genetic structures and prior phylogeographic information seems essential to conserve once widespread species.