The genetic structure of 10 populations (453 individuals) of stone loach (Barbatula barbatula L.), a small bottom-dwelling cyprinid fish, in the littoral zone of Lake Constance, central Europe, was investigated by analysing the mitochondrial control region sequences and five microsatellite loci. An unexpectedly high degree of genetic diversity (up to 0.36%) and old estimated age of these populations (> 150 000 years) based on mitochondrial DNA (mtDNA) was found. These findings contrast with the relatively young age of the lake, which could be colonized by fish only after the last ice age around 15 000 bp. Stone loach appears to be an old species in a young lake. Both types of molecular markers showed population genetic structure pronounced in mtDNA (overall F(ST) = 0.15) but moderate in microsatellites (F(ST) = 0.03). As predicted by its life history, philopatry, and limited capacity for dispersal, stone loach populations of Lake Constance show a clear pattern of isolation by distance. Geographic distances along the shores are the best explanation for the observed geographical distribution of genetic differentiation (r = 0.88), indicating that open water represents a barrier for the dispersal of the stone loach. The colonization of Lake Constance might have occurred initially at one location and then populations spread throughout the lake in a stepwise manner following the shoreline, and subsequently remained largely genetically isolated as suggested by the large observed differences among them.