Phasmatodea represents an order of hemimetabolous insects. This group includes species with extreme forms of masquerade crypsis, whereby they imitate twigs, bark, lichen, moss, and leaves. In this study, we sequenced and annotated three mitochondrial genomes (mitogenomes) from Phasmatodea. The lengths of the novel mitogenomes range from 14,162 bp to 15,879 bp. The gene content and organization correspond to those inferred for the ancestral insect. We conducted phylogenetic analyses together with the existing mitogenomes of polyneopterans and mayflies. In most cases, the Phasmatodea was non-monophyletic, with Embioptera and Zoraptera nested inside. The mitogenome sequences from Embioptera and Zoraptera suffered from high substitution rates and displayed very long branches in phylogenetic trees. The monophyletic Phasmatodea was recovered only when the analysis employed the site-heterogeneous CAT-GTR model in PhyloBayes and used the nucleotide dataset PCG_nt. The Euphasmatodea was well established by various data types and inference methods. In addition, the clade Heteropterygidae and the subfamilies Lonchodinae and Necrosciinae were strongly supported. The Australasian clade Lanceocercata was recovered across analyses. However, the Clitumninae was non-monophyletic.