The relationships of 25 different populations of the genus Barbus s. str. have been studied using different parsimony grouping methods and similarity indexes. The results indicate that Barbus s. str. is composed of two different groups. They are provisionally placed into two different subgenera (Barbus and Luciobarbus) in order to make the taxonomic work easier. The European species (B. barbus, B. plebejus, B. ciscaucasicus, B. cyclolepis, B. petenyi, B. haasi and B. meridionalis) are included in the subgenus Barbus. Within this group there are two evolutionary lines, one formed by central European species and the other by Mediterranean species which live in mountain fluvial courses. The subgenus Luciobarbus is constituted by Iberian, northern African and Asian species. The relationships between them are not satisfactorily resolved. Two northern African species (B. nasus and B.magniatlantis) are not included in any subgenus, as their phylogenetic relationships are not clear enough. The fossil record of this genus has been reviewed and new remains from the middle Miocene of Spain are reported as being the earliest known fossils of the genus Barbus. The first known fossils of Luciobarbus date from the Upper Miocene in Spain, Africa and Asia. The dispersion of Barbus in two main periods is postulated, one of them during the main Alpine orogenic phase at the end of the Oligocene, the other during the Upper Miocene transgression. The first one maybe favoured Barbus and the second Luciobarbus. Barriers that might have fragmented the different populations of the genus Barbus have been evaluated and a comprehensive biogeographic model, which minimizes the dispersion events, is proposed.