Phylogenetic relationships and evolutionary patterns in the genus Barbus were examined through the analysis of the complete sequences of three mitochondrial genes: ATPases 8 and 6, which overlap slightly, and cytochrome b. This complex genus includes diploid as well as tetraploid and hexaploid species that are distributed throughout the Palaearctic, Ethiopian and Asiatic biogeographical regions. Given that genome duplication is an important evolutionary mechanism in eukaryotes, in the present report we attempt to describe its role in the evolution of the genus Barbus, as well as drawing systematic and phylogenetic conclusions. The phylogenetic results indicated the splitting of the current Barbus genus into five main mitochondrial lineages corresponding to (i) the genus Barbus sensu stricto (tetraploid, which is subdivided into the subgenera Barbus and Luciobarbus), (ii) the hexaploid species, (iii) the Ethiopian tetraploid species, (iv) the African diploid species, and (v) the Asian diploid species. The branching of ‘foreign’ genera as sister groups of some of these monophyletic assemblages (such as Aulopyge is to Barbus sensu stricto or Varicorhinus is to the hexaploid barbels) demonstrates the polyphyly of the group. Moreover, the relationships between the proposed lineages also show that genome duplication may be considered as a homoplasic character since it must have occurred over at least three independent periods and/or in three independent areas. In relation to the possible saltational evolutionary model for the polyploid species examined here, it was found that, although feasible at the nuclear level, the mitochondrial markers looked at do not appear to have undergone this type of evolution. Rather, they seem to have experienced more or less constant change through time.