Background Leuciscinae is a subfamily belonging to the Cyprinidae fish family that is widely distributed in Circum-Mediterranean region. Many efforts have been carried out to deciphering the evolutionary history of this group. Thus, different biogeographical scenarios have tried to explain the colonization of Europe and Mediterranean area by cyprinids, such as the "north dispersal" or the "Lago Mare dispersal" models. Most recently, Pleistocene glaciations influenced the distribution of leuciscins, especially in North and Central Europe. Weighing up these biogeographical scenarios, this paper constitutes not only the first attempt at deciphering the mitochondrial and nuclear relationships of Mediterranean leuciscins but also a test of biogeographical hypotheses that could have determined the current distribution of Circum-Mediterranean leuciscins. Results A total of 4439 characters (mitochondrial + nuclear) from 321 individuals of 176 leuciscine species rendered a well-supported phylogeny, showing fourteen main lineages. Analyses of independent mitochondrial and nuclear markers supported the same main lineages, but basal relationships were not concordant. Moreover, some incongruence was found among independent mitochondrial and nuclear phylogenies. The monophyly of some poorly known genera such as Pseudophoxinus and Petroleuciscus was rejected. Representatives of both genera belong to different evolutionary lineages. Timing of cladogenetic events among the main leuciscine lineages was gained using mitochondrial and all genes data set. Conclusions Adaptations to a predatory lifestyle or miniaturization have superimposed the morphology of some species. These species have been separated into different genera, which are not supported by a phylogenetic framework. Such is the case of the genera Pseudophoxinus and Petroleuciscus, which real taxonomy is not well known. The diversification of leuciscine lineages has been determined by intense vicariant events following the paleoclimatological and hydrogeological history of Mediterranean region. We propose different colonization models of Mediterranean region during the early Oligocene. Later vicariance events promoted Leuciscinae diversification during Oligocene and Miocene periods. Our data corroborate the presence of leuciscins in North Africa before the Messinian salinity crisis. Indeed, Messinian period appears as a stage of gradually Leuciscinae diversification. The rise of humidity at the beginning of the Pliocene promoted the colonization and posterior isolation of newly established freshwater populations. Finally, Pleistocene glaciations determined the current European distribution of some leuciscine species.