We have genetically retrieved, resurrected and performed detailed structure-function analyses on authentic woolly mammoth hemoglobin to reveal for the first time both the evolutionary origins and the structural underpinnings of a key adaptive physiochemical trait in an extinct species. Hemoglobin binds and carries O(2); however, its ability to offload O(2) to respiring cells is hampered at low temperatures, as heme deoxygenation is inherently endothermic (that is, hemoglobin-O(2) affinity increases as temperature decreases). We identify amino acid substitutions with large phenotypic effect on the chimeric beta/delta-globin subunit of mammoth hemoglobin that provide a unique solution to this problem and thereby minimize energetically costly heat loss. This biochemical specialization may have been involved in the exploitation of high-latitude environments by this African-derived elephantid lineage during the Pleistocene period. This powerful new approach to directly analyze the genetic and structural basis of physiological adaptations in an extinct species adds an important new dimension to the study of natural selection.