The family Gyrodactylidae contains one of the most significant radiations of platyhelminth fish parasites. The so-called hyperviviparity is very rare in the animal kingdom, and the rapid generation time can lead to an explosive population growth, which can cause massive losses in farmed fish. Here we present the first molecular phylogeny including all-but-one African genera, inferred from ITS and 18S rDNA sequences. The validity of nominal genera is discussed in relation to the systematic value of morphological characters traditionally used for generic identification. New complete 18S rDNA sequences of 18 gyrodactylid species of eight genera together with ITS rDNA gene sequences of eight species representing seven genera were generated and complemented with GenBank sequences. The maximum likelihood and Bayesian analyses pointed to a paraphyletic nature of African Gyrodactylus species. They formed well-supported clades possibly indicating speciation within host taxa: (1) parasites of cichlids (Cichlidae); (2) parasites of catfishes (Siluriformes), consisting of a lineage infecting mochokids and one infecting clariids. Macrogyrodactylus spp. firmly clustered into a monophyletic group. We found that Swingleus and Fundulotrema are very closely related and clearly cluster within Gyrodactylus. This supports earlier claims as to the paraphyly of the nominal genus Gyrodactylus as it is currently defined, and necessitates a revision of Swingleus and Fundulotrema. Molecular dating estimates confirmed a relatively young, certainly post-Gondwanan, origin of gyrodactylid lineages. Building on the previously suggested South-American origin of viviparous gyrodactylids, the dataset suggests subsequent intercontinental dispersal to Africa and from there repeated colonisation of the Holarctic. Even though the African continent has been heavily under sampled, the present diversity is far greater than in the intensively studied European fauna, probably because of the high endemicity of sub-Saharan Africa.