We had previously shown that sperm from men harbouring haplogroup T mtDNAs swim less vigorously than those from haplogroup H. However, the biochemical basis of this motility was difficult to investigate because of the multiple mutations, the most important of which affected respiratory complex I for which there is no crystal structure. To more thoroughly study the relationship between mtDNA variation and differences in mitochondrial energy metabolism, we turned to the analysis of sperm baring haplogroup U mtDNAs. Haplogroup U is a monophyletic ancient and thus heterogeneous maternal lineage that is broadly distributed among European individuals. Several sublineages of haplogroup U were found to be associated with differences in sperm motility and vitality. These differences could be related to a highly conserved missense mutation in the mtDNA COIII gene (V91) and several equally conserved mutations in the cytochrome b (cytb) gene. Moreover, the lineages with the cytb mutations were substantially enriched in northern Europe, while those lacking these mutations were more prevalent in southern Europe. We suggest that some of these ancient conserved cytb missense mutations permitted our ancestors to adapt to cold by partially uncoupling mitochondrial oxidative phosphorylation (OXPHOS).