The polyphyletic nature of the tapeworm order Tetraphyllidea Carus, 1863 is addressed in part with the establishment of the new order Rhinebothriidea for a subset of the taxa formerly comprising the phyllobothriid subfamily Rhinebothriinae (Platyhelminthes: Eucestoda). Support for the order comes from Bayesian, maximum likelihood, and parsimony analyses of complete ssrDNA and partial (D1-D3) lsrDNA sequence data for 58 cestode species. These data consisted of novel data generated for 40 species in 15 genera of candidate rhinebothriines and the cathetocephalidean species Sanguilevator yearsleyi as well as comparable data taken from GenBank for an additional 18 cestode species in 17 genera. In total, the species analyzed consisted of two Cathetocephalidea, two Litobothriidea, two Lecanicephalidea, three Proteocephalidea, and 49 Tetraphyllidea. The tetraphyllideans consisted of three Onchobothriidae, three Serendipidae, and 43 Phyllobothriidae (one Thysanocephalinae, one Echeneibothriinae, five Phyllobothriinae, 35 candidate Rhinebothriinae and the poorly known Spongiobothrium). This work suggests that some elements of current membership in the group are in need of revision. For example, while inclusion of the echeneibothriine genus Echeneibothrium and the phyllobothriine genera Rhodobothrium and Anthocephalum, and also Spongiobothrium, in the Rhinebothriidea is supported, inclusion of Duplicibothrium and Caulobothrium in the new order is not. Histological sections and scanning electron microscopy of selected members of the study group suggest that the presence of bothridial stalks may serve as an effective morphological feature to characterise the order. The group is restricted to elasmobranchs, and appears to have a particular affinity for Myliobatiformes. The new order includes at least 13 genera. Intraordinal relationships were determined to be insufficiently stable to justify the formal reorganization of rhinebothriidean families at this time.