The combination of exceptionally high species diversity, high host specificity, and a complex reproduction system raises many questions about the underlying mechanisms triggering speciation in the flatworm genus Gyrodactylus. The coevolutionary history with their goby hosts was investigated using both topology- and distance-based approaches; phylogenies were constructed of the V4 region of the 18S rRNA and the complete ITS rDNA region for the parasites, and 12S and 16S mtDNA fragments for the hosts. The overall fit between both trees was significant according to the topology-based programs (TreeMap 1.0, 2.0 beta and TreeFitter), but not according to the timed analysis in TreeMap 2.0 beta and the distance-based method (ParaFit). An absolute timing of speciation events in host and parasite ruled out the possibility of synchronous speciation for the gill parasites, favouring the distance-based result. Based on this information together with the biological background of host and parasite, the following TreeMap solution was selected. The group of gill parasites evolved from a host switch from G. arcuatus, parasitizing the three-spined stickleback onto the gobies, followed by several host-switching events among the respective goby hosts. The timing of these events is estimated to date back to the Late Pleistocene, suggesting a role for refugia-mediated mixing of parasite species. In contrast, it is suggested that co-speciation in the fin-parasites resulted in several host-associated species complexes. This illustrates that phylogenetically conserved host-switching mimics the phylogenetic signature of co-speciation, confounding topology-based programs.