Long non-coding regions (NCRs) and gene rearrangements are commonly seen in mitochondrial genomes of Mantodea and are primarily focused on three regions: CR-I-Q-M-ND2, COX2-K-D-ATP8, and ND3-A-R-N-S-E-F-ND5. In this study, eight complete and one nearly complete mitochondrial genomes of praying mantises were acquired for the purpose of discussing mitochondrial gene rearrangements and phylogenetic relationships within Mantodea, primarily in the newly established families Haaniidae and Gonypetidae. Except for Heterochaeta sp. JZ-2017, novel mitochondrial gene arrangements were detected in Cheddikulama straminea, Sinomiopteryx graham, Pseudovates chlorophaea, Spilomantis occipitalis. Of note is the fact that one type of novel arrangement was detected for the first time in the Cyt b-S2-ND1 region. This could be reliably explained by the tandem replication-random loss (TDRL) model. The long NCR between trnT and trnP was generally found in Iridopteryginae and was similar to the ND4L or ND6 gene. Combined with gene rearrangements and intergenic regions, the monophyly of Haaniidae was supported, whereas the paraphyly of Gonypetidae was recovered. Furthermore, several synapomorphies unique to some clades were detected that conserved block sequences between trnI and trnQ and gaps between trnT and trnP in Toxoderidae and Iridopteryginae, respectively.