We determined the complete mitochondrial (mt) genomes of three evaniomorph species, Ceraphron sp. (Ceraphronoidea), Gasteruption sp. (Evanioidea), and Orthogonalys pulchella (Trigonalyoidea) as well as the nearly complete mt genome from another evaniomorph species, Megalyra sp. (Megalyroidea). Each of them possesses dramatic gene rearrangements, including protein-coding or rRNA genes. Gene inversions were identified in all of these mt genomes; for example, the two rRNA genes have inverted and moved into the nad2-cox1 junction in the Megalyra sp. mt genome. In addition, we found two copies of a 10-bp complementary repeat at the beginning of rrnS and at the end of trnL2 in the Gasteruption sp. mt genome, consistent with recombination as the possible mechanism for gene inversion and long-range movement. Although each of the genomes contains a number of repeats of varying size, there was no consistent association of the size or number of repeats with the extent or type of gene rearrangement. The breakpoint distance analysis showed the Evaniomorpha has an intermediate rate of gene rearrangement. Sequence-based phylogenetic analyses of 13 protein-coding and 2 rRNA genes in 22 hymenopteran taxa recovered a paraphyletic Evaniomorpha with the Aculeata nested within it. Within the Evaniomorpha, our analyses confirmed the Trigonalyoidea + Megalyroidea as the sister group to the Aculeata and recovered a novel clade, Ceraphronoidea + Evanioidea. In contrast to previous hymenopteran phylogenetic studies, the internal relationships of the Evaniomorpha were highly supported and robust to the variation of alignment approach and phylogenetic inference approach.