Gyrodactylus is a lineage of monogenean flatworm ectoparasites exhibiting many features that make them a suitable model to study their co-evolution with fish hosts. Previous co-evolutionary studies of this lineage mainly relied on low-power datasets (a small number of samples and a single molecular marker), and (now) outdated algorithms. To investigate the coevolutionary relationship of gyrodactylids and their fish hosts in high resolution, we used complete mitogenomes (including two newly sequenced Gyrodactylus species), a large number of species in the single-gene dataset, and four different coevolutionary algorithms. The overall co-evolutionary fit between the parasites and hosts was consistently significant. Multiple indicators support gyrodactylids as highly host-specific parasites, but few gyrodactylids can parasitize either multiple (more than 5) or phylogenetically-distant fish hosts. The molecular dating results indicate they tend to evolve towards high host specificity. Speciation by host-switching is a more important speciation mode than co-speciation for them. Assuming the origin on Cypriniformes, we inferred four major host switch events to non-Cypriniformes hosts (mostly Salmoniformes) occurred deep in the evolutionary history. Despite their relative rarity, these events had strong macroevolutionary consequences for gyrodactylid diversity. For example, in our dataset, 57.28% of all studied gyrodactylids parasitised only non-Cypriniformes hosts, which implies that the evolutionary history of more than half of all included lineages could be traced back to these major host switch events. Geographical co-occurrence of fishes and gyrodactylids determined the host use by these gyrodactylids, and geography accounted for most of the phylogenetic signal in host use.