Natural colonizations across watersheds have been frequently proposed to explain the present distributions of many freshwater fish species. However, detailed studies of such potential watershed crossings are still missing. Here, we investigated potential postglacial watershed crossings of the widely distributed European bullhead (Cottus gobio L.) in two different areas along the Rhine-Rhône watershed using detailed genetic analysis. The main advantage of studying bullheads vs. other freshwater fish species is that their distribution has been lightly influenced by human activities and as such, interpretations of colonization history are not confounded by artificial transplantations. The genetic analyses of eight microsatellite loci revealed strong genetic similarities between populations of both sides of the Rhine-Rhône watershed in the Lake Geneva area, giving strong evidence for a natural watershed crossing of bullheads from the upper Rhine drainage into the Rhône drainage in the Lake Geneva area likely facilitated by the retreat of the glaciers after the last glacial maximum some 20,000 years ago. Populations from the Lake Geneva basin were genetically more similar to populations from across the watershed in the upper Rhine drainage than to populations further downstream in the lower Rhône. In contrast, populations from Belfort, an area, which was not covered by ice during the last glacial maximum, showed strong genetic differentiation between populations of the upper Rhine and Rhône drainages. Based on our results on the bullhead, we propose that glacial retreat may have eased the dispersal of numerous European freshwater fish species across several geological boundaries.