In a manner similar to many other groups of organisms, the tapeworm order Proteocephalidea poses a difficult phylogenetic problem if treated on the basis of single-gene analysis. Since the biogeography and host distribution of proteocephalideans make these tapeworms a potentially interesting model for evolutionary and co-evolutionary studies, we tried to resolve their phylogenetic relationships by applying a multi-gene approach. The ITS2 sequences and V4 hypervariable loop of 18S rRNA were obtained for 43 and 35 proteocephalidean taxa, respectively, and combined with other sequences available in the GenBank. The phylogenetic analysis of the combined DNA set was confronted with characters derived from ITS2 secondary structures. Using this approach, a species-rich Neotropical lineage of proteocephalideans could be reliably resolved. The phylogenetic relationships within this group show a high degree of phylogeny-independent host distribution. The reconstruction of ITS2 secondary structure revealed a universal 4-domain arrangement, which is conserved across a wide range of Neodermata. Several motifs of the secondary structure could be mapped to the phylogenetic tree as possible clade synapomorphies.