Gregarines from the families Dactylophoridae and Trichorhynchidae parasitize exclusively centipedes and have a distinct morphology among other terrestrial eugregarines, but their evolutionary relationships have not yet been studied with molecular methods. Here we obtain rDNA operon sequences for the dactylophorids and trichorhynchids. We describe a new species Trichorhynchus efeykini sp. n. from a scutigeromorph Thereuopoda longicornis from Vietnam. Phylogenetic analyses with combined SSU, 5.8S and LSU rDNA dataset support the previously proposed separation of Trichorhynchus to the Trichorhynchidae based on morphology and recover the dactylophorids and trichorhynchids as sister groups in a monophyletic clade. This clade appears sister to the clade of the Actinocephaloidea and Stylocephaloidea, and represents a new major lineage of terrestrial gregarines that we designate as a new superfamily Dactylophoroidea.