We estimated the phylogenetic relationships of all Ibero-African spined loaches of the genus Cobitis using the complete mitochondrial cytochrome b gene (1140bp). We analysed 93 individuals of seven cobitid species found in all the principal drainages of the Iberian Peninsula and North Africa. A molecular phylogeny was used to revise current systematics of the Ibero-African Cobitis species and to infer a biogeographical model for Cobitis in the Western Mediterranean area during the Cenozoic period. Phylogenetic analysis provided support for the monophyly of two mtDNA clades: Clade A or Italian Clade with the Italian species (C. bilineata, C. zanandreai), and Clade B or the Ibero-African Clade. The Ibero-African Clade included all species endemic for the Iberian Peninsula (C. vettonica, C. calderoni, and C. paludica) and North Africa (C. maroccana). The species C. paludica does not constitute a natural group, and could be divided into at least four monophyletic mtDNA lineages with moderate to high bootstrap values and posterior probability support. Phylogenetic relationships of the Ibero-African species were not resolved satisfactorily, but in all analyses C. calderoni from Northern Iberian Peninsula was basal. We have re-calibrated a molecular clock for the genus Cobitis (0.68% per million year by pairwise) using populations inhabiting both sides of the Gibraltar Strait. Application of this Cobitis mtDNA clock provides evidence that the Messinian salinity crisis played a primary role in the diversification of some Ibero-African cobitid species. The basal polytomies of the Ibero-African Clade might suggest that all mtDNA lineages diversified rapidly.