The Acanthocephala is a phylum of obligate endoparasitic animals comprising four classes (Archiacanthocephala, Palaeacanthocephala, Eoacanthocephala and Polyacanthocephala), although the phylogenetic interrelationships of these classes still remains unresolved. To investigate phylogenetic relationships of major acanthocephalan groups, we characterized the complete mitochondrial genome sequences of two palaeacanthocephalan species Centrorhynchus aluconis and Prosthorhynchus transversus (representing two different families of the order Polymorphida), and Polyacanthorhynchus caballeroi (the first mitogenomic representative of the class Polyacanthocephala) and used these new sequences for phylogenetic analyses, along with 32 platyzoan mtDNAs, including 10 additional acanthocephalans. Phylogenetic analyses using concatenated amino acid sequences for 12 protein-coding genes with maximum likelihood and Bayesian inference methods supported monophyly of Acanthocephala. Within the phylum, Archiacanthocephala was positioned as the sister to the clade containing all three other acanthocephalan classes, with the polyacanthocephalan species P. caballeroi nested within Eoacanthocephala. This result contradicts morphology-based classification systems that treated polyacanthorhynchids as one of the palaeacanthocephalan families, and instead suggests Polyacanthocephala is a member of Eoacanthocephala. Within the Palaeacanthocephala, Polymorphida monophyly was strongly supported and this is inconsistent with nuclear rDNA-based molecular hypotheses that suggest non-monophyly.