The relationships between parasites and their hosts are intimate, dynamic and complex; the evolution of one is inevitably linked to the other. Despite multiple origins of parasitism in the Cnidaria, only parasites belonging to the Myxozoa are characterized by a complex life cycle, alternating between fish and invertebrate hosts, as well as by exceptionally high species diversity. This inspired us to examine the history of reciprocal interactions and adaptive radiations in myxozoans and their hosts by determining the degree of congruence between their phylogenies and by timing the emergence of myxozoan lineages in relation to their hosts. Recent genomic analyses suggested a common origin of Polypodium hydriforme, a cnidarian parasite of acipenseriform fishes, and the Myxozoa, and proposed fish as original hosts for both sister lineages. We clearly demonstrate that the Myxozoa emerged long before fish populated Earth and that phylogenetic congruence with their invertebrate hosts is evident down to the most basal branches of the tree, indicating bryozoans and annelids as original hosts and challenging previous hypothesis. We provide evidence that, following invertebrate invasion, fish hosts were acquired multiple times, leading to parallel cospeciation patterns in all major phylogenetic lineages. We identify the acquisition of vertebrate hosts that facilitate alternative transmission and dispersion strategies as reason for the distinct success of the Myxozoa, and identify massive host specification-linked parasite diversification events. The results of this study transform our understanding of the origins and evolution of parasitism in the most basal metazoan parasites known.