Tapeworms of the order Caryophyllidea are the earliest diverging ‘true’ tapeworms (Eucestoda) and parasitise almost exclusively cypriniform and siluriform fishes. They are typified by a monozoic, i.e., non-proglottised body plan, which is a characteristic shared with early diverging ‘cestodarians’ Gyrocotylidea and Amphilinidea. Here we present the most comprehensive multi-gene molecular phylogeny of this group, to date. Specimens of 61 species from 31 genera (~50% and ~75% of known species and genus diversity, respectively) were gathered during an intense and targeted 15-year collecting effort. Phylogenetic reconstructions provide high nodal support for three major lineages, which only partly correspond to currently recognised families. The three well-supported clades were as follows: Clade A was in an unsupported position at the base of the tree and was almost exclusively comprised of parasites of catfishes (Siluriformes) from the Ethiopian and Oriental regions, including the type genus of the Lytocestidae (Lytocestus). Clade B formed the sister group to the remaining taxa (Clade C) and was composed of species that parasitise cyprinids and loaches (Cypriniformes: Cyprinoidei and Cobitoidei) from the Palaearctic Region. This clade included the type genus of the Caryophyllaeidae (Caryophyllaeus). Clade C comprised Nearctic species from suckers and minnows (Cypriniformes: Catostomidae and Cyprinoidei), which were previously accommodated in two families, i.e. Capingentidae and Caryophyllaeidae. This clade included the type genus of the Capingentidae (Capingens). In addition to Clades A–C, Balanotaenia bancrofti from the monotypic Balanotaeniidae, which parasitises plotosid catfishes in Australia, and Lytocestoides tanganyikae, which parasitises African cichlids, formed a poorly-supported clade at the base of the tree. Whereas morphological characteristics traditionally used to differentiate caryophyllidean families do not characterise molecular lineages, host association and biogeographical distribution play a key role in the circumscription of the three well-supported clades revealed by molecular data. Thus, the taxonomic rearrangement proposed herein was guided by the molecular clades. The names of all four extant families were preserved and family affinity was determined by topological clustering with the type genera of the families. The family diagnoses of the Lytocestidae, Caryophyllaeidae and Capingentidae are amended. Biogeographic patterns are indicative of separate Gondwanan and Laurasian radiations having taken place. Regarding the Gondwanan radiation in the Siluriformes, the topology in Clade A indicates an Asian origin with a subsequent African colonisation. Regarding Laurasia, separate radiations appear to have taken place in the Cypriniformes in the temperate zones of North America and Eurasia. Complete absence of caryophyllideans in the Neotropical Region, where numerous catfishes occur, may be due to the Gondwanan radiation having taken place after the separation of Africa and South America.