Collembola are a basal group of Hexapoda renowned for both unique morphological characters and significant ecological roles. However, a robust and plausible phylogenetic relationship between its deeply divergent lineages has yet to be achieved. We carried out a mitophylogenomic study based on a so far the most comprehensive mitochondrial genome dataset. Our data matrix contained mitogenomes of 31 species from almost all major families of all four orders, with 16 mitogenomes newly sequenced and annotated. We compared the linear arrangements of genes along mitochondria across species. Then we conducted 13 analyses each under a different combination of character coding, partitioning scheme and heterotachy models, and assessed their performance in phylogenetic inference. Several hypothetical tree topologies were also tested. Mitogenomic structure comparison revealed that most species share the same gene order of putative ancestral pancrustacean pattern, while seven species from Onychiuridae, Poduridae and Symphypleona bear different levels of gene rearrangements, indicating phylogenetic signals. Tomoceroidea was robustly recovered for the first time in the presence of all its families and subfamilies. Monophyly of Onychiuroidea was supported using unpartitioned models alleviating LBA. Paronellidae was revealed polyphyletic with two subfamilies inserted independently into Entomobryidae. Although Entomobryomorpha has not been well supported, more than half of the analyses obtained convincing topologies by placing Tomoceroidea within or near remaining Entomobryomorpha. The relationship between elongate-shaped and spherical-shaped collembolans still remained ambiguous, but Neelipleona tend to occupy the basal position in most trees. This study showed that mitochondrial genomes could provide important information for reconstructing the relationships among Collembola when suitable analytical approaches are implemented. Of all the data refining and model selecting schemes used in this study, the combination of nucleotide sequences, partitioning model and exclusion of third codon positions performed better in generating more reliable tree topology and higher node supports than others.