The mammoths originated in warm and equatorial Africa and later colonized cold and high-latitude environments. Studies on nuclear genes suggest that woolly mammoth had evolved genetic variations involved in processes relevant to cold tolerance, including lipid metabolism and thermogenesis, and adaptation to extremely varied light and darkness cycles. The mitochondria is a major regulator of cellular energy metabolism, thus the mitogenome of mammoths may also exhibit adaptive evolution. However, little is yet known in this regard. In this study, we analyzed mitochondrial protein-coding genes (MPCGs) sequences of 75 broadly distributed woolly mammoths (Mammuthus primigenius) to test for signatures of positive selection. Results showed that a total of eleven amino acid sites in six genes, namely ND1, ND4, ND5, ND6, CYTB, and ATP6, displayed strong evidence of positive selection. Two sites were located in close proximity to proton-translocation channels in mitochondrial complex I. Biochemical and homology protein structure modeling analyses demonstrated that five amino acid substitutions in ND1, ND5, and ND6 might have influenced the performance of protein–protein interaction among subunits of complex I, and three substitutions in CYTB and ATP6 might have influenced the performance of metabolic regulatory chain. These findings suggest metabolic adaptations in the mitogenome of woolly mammoths in relation to extreme environments and provide a basis for further tests on the significance of the variations on other systems.