Elucidating genetic mechanisms of adaptation is a goal of central importance in evolutionary biology, yet few empirical studies have succeeded in documenting causal links between molecular variation and organismal fitness in natural populations. Here we report a population genetic analysis of a two-locus α-globin polymorphism that underlies physiological adaptation to high-altitude hypoxia in natural populations of deer mice, Peromyscus maniculatus. This system provides a rare opportunity to examine the molecular underpinnings of fitness-related variation in protein function that can be related to a well-defined selection pressure. We surveyed DNA sequence variation in the duplicated α-globin genes of P. maniculatus from high- and low-altitude localities (i) to identify the specific mutations that may be responsible for the divergent fine-tuning of hemoglobin function and (ii) to test whether the genes exhibit the expected signature of diversifying selection between populations that inhabit different elevational zones. Results demonstrate that functionally distinct protein alleles are maintained as a long-term balanced polymorphism and that adaptive modifications of hemoglobin function are produced by the independent or joint effects of five amino acid mutations that modulate oxygen-binding affinity.