Praying mantises are distributed all over the world. Though some Mantodea mitogenomes have been reported, an evolutionary genomic and phylogenetic analysis study lacks the latest taxonomic system. In the present study, four new mitogenomes were sequenced and annotated. Deroplatys truncate, D. lobate, Amorphoscelis chinensis and Macromantis sp. belong to Deroplatyidae, Amorphoscelidae and Photinaidae family, respectively. Our results indicated that the ATP8 gene may be lost in D. truncate and D. lobata mt genome, and four tRNA genes have not been found in D. truncate, D. lobata and Macromantis sp. A dN/dS pair analysis was conducted and it was found that all genes have evolved under purifying selection. Furthermore, we tested the phylogenetic relationships between the eight families of the Mantodea, including 35 species of praying Mantis. Based on the complete mitochondrial genome data, it was also suggested as sister to Deroplatyidae + Mantidae, Metallyticus sp., the only representative of Metallyticidae, is sister to the remaining mantises. Our results support the taxonomic system of Schwarz and Roy and are consistent with previous studies.