Despite the mitochondrion's long-recognized role in energy production, mitochondrial DNA (mtDNA) variation commonly found in natural populations was assumed to be effectively neutral. However, variation in mtDNA has now been increasingly linked to phenotypic variation in life history traits and fitness. We examined whether the relative fitness in native and invasive common wasp (Vespula vulgaris) populations in Belgium and New Zealand (NZ), respectively, can be linked to mtDNA variation. Social wasp colonies in NZ were smaller with comparatively fewer queen cells, indicating a reduced relative fitness in the invaded range. Interestingly, queen cells in this population were significantly larger leading to larger queen offspring. By sequencing 1,872 bp of the mitochondrial genome, we determined mitochondrial haplotypes and detected reduced genetic diversity in NZ. Three common haplotypes in NZ frequently produced many queens, whereas the four rare haplotypes produced significantly fewer or no queens. The entire mitochondrial genome for each of these haplotypes was sequenced to identify polymorphisms associated with fitness reduction. We found 16 variable sites; however, no nonsynonymous mutation that was clearly causing impaired mitochondrial function was detected. We discuss how detected variants may alter secondary structures, gene expression or mito-nuclear interactions, or could be associated with nuclear-encoded variation. Whatever the ultimate mechanism, we show reduced fitness and mtDNA variation in an invasive wasp population as well as specific mtDNA variants associated with fitness variation within this population. Ours is one of only a few studies that confirm fitness impacts of mtDNA variation in wild nonmodel populations.