Investigating processes and timing of differentiation of organisms is critical in the understanding of the evolutionary mechanisms involved in microevolution, speciation, and macroevolution that generated the extant biodiversity. From this perspective, the Telestes genus is of special interest: the Telestes species have a wide distribution range across Europe (from the Danubian district to Mediterranean districts) and have not been prone to translocation. Molecular data (mtDNA: 1,232 bp including the entire Cyt b gene; nuclear genome: 11 microsatellites) were gathered from 34 populations of the Telestes genus, almost encompassing the entire geographic range. Using several phylogenetic and molecular dating methods interpreted in conjunction with paleoclimatic and geomorphologic evidence, we investigated the processes and timing of differentiation of the Telestes lineages. The observed genetic structure and diversity were largely congruent between mtDNA and microsatellites. The Messinian Salinity Crisis (Late Miocene) seems to have played a major role in the speciation processes of the genus. Focusing on T. souffia, a species occurring in the Danube and Rhone drainages, we were able to point out several specific events from the Pleistocene to the Holocene that have likely driven the differentiation and the historical demography of this taxon. This study provides support for an evolutionary history of dispersal and vicariance with unprecedented resolution for any freshwater fish in this region.