Phylogenetic relationships of basal insects remain a matter of discussion. In particular, the relationships among Ephemeroptera, Odonata and Neoptera are the focus of debate. In this study, we used a next-generation sequencing approach to reconstruct new mitochondrial genomes (mitogenomes) from 18 species of basal insects, including six representatives of Ephemeroptera and 11 of Odonata, plus one species belonging to Zygentoma. We then compared the structures of the newly sequenced mitogenomes. A tRNA gene cluster of IMQM was found in three ephemeropteran species, which may serve as a potential synapomorphy for the family Heptageniidae. Combined with published insect mitogenome sequences, we constructed a data matrix with all 37 mitochondrial genes of 85 taxa, which had a sampling concentrating on the palaeopteran lineages. Phylogenetic analyses were performed based on various data coding schemes, using maximum likelihood and Bayesian inferences under different models of sequence evolution. Our results generally recovered Zygentoma as a monophyletic group, which formed a sister group to Pterygota. This confirmed the relatively primitive position of Zygentoma to Ephemeroptera, Odonata and Neoptera. Analyses using site-heterogeneous CAT-GTR model strongly supported the Palaeoptera clade, with the monophyletic Ephemeroptera being sister to the monophyletic Odonata. In addition, a sister group relationship between Palaeoptera and Neoptera was supported by the current mitogenomic data.