The infraorder Cephalobomorpha is a diverse and ecologically important nematode group found in almost all terrestrial environments. In a recent nematode classification system based on SSU rDNA, Cephalobomorpha was classified within the suborder Tylenchina with Panagrolaimomorpha, Tylenchomorpha and Drilonematomorpha. However, phylogenetic relationships among species within Tylenchina are not always consistent, and the phylogenetic position of Cephalobomorpha is still uncertain. In this study, in order to examine phylogenetic relationships of Cephalobomorpha with other nematode groups, we determined the complete mitochondrial genome sequence of Acrobeloides varius, the first sequenced representative of Cephalobomorpha, and used this sequence for phylogenetic analyses along with 101 other nematode species. Phylogenetic analyses using amino acid and nucleotide sequence data of 12 protein-coding genes strongly support a sister relationship between the two cephalobomorpha species A. varius and Acrobeles complexus (represented by a partial mt genome sequence). In this mitochondrial genome phylogeny, Cephalobomorpha was sister to all chromadorean species (excluding Plectus acuminatus of Plectida) and separated from Panagrolaimomorpha and Tylenchomorpha, rendering Tylenchina non-monophyletic. Mitochondrial gene order among Tylenchina species is not conserved, and gene clusters shared between A. varius and A. complexus are very limited. Results from phylogenetic analysis and gene order comparison confirms Tylenchina is not monophyletic. To better understand phylogenetic relationships among Tylenchina members, additional mitochondrial genome information is needed from underrepresented taxa representing Panagrolaimomorpha and Cephalobomorpha.