Praying mantises are a diverse group of predatory insects. Although some Mantodea mitogenomes have been reported, a comprehensive comparative and evolutionary genomic study is lacking for this group. In the present study, four new mitogenomes were sequenced, annotated, and compared to the previously published mitogenomes of other Mantodea species. Most Mantodea mitogenomes share a typical set of mitochondrial genes and a putative control region (CR). Additionally, and most intriguingly, another large non-coding region (LNC) was detected between trnM and ND2 in all six Paramantini mitogenomes examined. The main section in this common region of Paramantini may have initially originated from the corresponding control region for each species, whereas sequence differences between the LNCs and CRs and phylogenetic analyses indicate that LNC and CR are largely independently evolving. Namely, the LNC (the duplicated CR) may have subsequently degenerated during evolution. Furthermore, evidence suggests that special intergenic gaps have been introduced in some species through gene rearrangement and duplication. These gaps are actually the original abutting sequences of migrated or duplicated genes. Some gaps (G5 and G6) are homologous to the 5' and 3' surrounding regions of the duplicated gene in the original gene order, and another specific gap (G7) has tandem repeats. We analysed the phylogenetic relationships of fifteen Mantodea species using 37 concatenated mitochondrial genes and detected several synapomorphies unique to species in some clades.