A monophyletic origin of endoparasitic thorny-headed worms (Acanthocephala) and wheel-animals (Rotifera) is widely accepted. However, the phylogeny inside the clade, be it called Syndermata or Rotifera, has lacked validation by mitochondrial (mt) data. Herein, we present the first mt genome of the key taxon Seison and report conflicting results of phylogenetic analyses: while mt sequence-based topologies showed monophyletic Lemniscea (Bdelloidea+Acanthocephala), gene order analyses supported monophyly of Pararotatoria (Seisonidea+Acanthocephala) and Hemirotifera (Bdelloidea+Pararotatoria). Sequence-based analyses obviously suffered from substitution saturation, compositional bias, and branch length heterogeneity; however, we observed no compromising effects in gene order analyses. Moreover, gene order-based topologies were robust to changes in coding (genes vs. gene pairs, two-state vs. multistate, aligned vs. non-aligned), tree reconstruction methods, and the treatment of the two monogonont mt genomes. Thus, mt gene order verifies seisonids as sister to acanthocephalans within monophyletic Hemirotifera, while deviating results of sequence-based analyses reflect artificial signal. This conclusion implies that the complex life cycle of extant acanthocephalans evolved from a free-living state, as retained by most monogononts and bdelloids, via an epizoic state with a simple life cycle, as shown by seisonids. Hence, Acanthocephala represent a rare example where ancestral transitional stages have counterparts amongst the closest relatives.