Higher-level hymenopteran relationships remain unresolved in both morphological and molecular analyses. In this study, we present the most comprehensive analyses of hymenopteran relationships based on 48 mitochondrial (mt) genomes. One complete and two nearly complete mt genomes representing three hymenopteran superfamilies were newly sequenced. We assessed the influence of inclusion/exclusion of 3rd codon positions, alignment approaches, partition schemes and phylogenetic approaches on topology and nodal support within the Hymenoptera. The results showed that the topologies were sensitive to the variation of dataset and analytical approach. However, some robust and highly supported relationships were recovered: the Ichneumonomorpha was monophyletic; the Trigonalyoidea+Megalyroidea and the Diaprioidea+Chalcidoidea were consistently recovered; the Cynipoidea was generally recovered as the sister group to the Diaprioidea+Chalcidoidea. In addition, the monophyletic Aculeata and Proctotrupomorpha were recovered in some analyses. Several gene rearrangements were detected in each of the three newly sequenced mt genomes. Specifically, the Ibalia leucospoides mt genome harbors a large inversion of a gene block from trnE to trnS2. Inverted, duplicated A+T rich regions were detected in the Ibalia leucospoides mt genome, which probably played an important role during the formation of the large gene block inversion via recombination.