Tibetans do not exhibit increased hemoglobin concentration at high altitude. We describe a high-frequency missense mutation in the EGLN1 gene, which encodes prolyl hydroxylase 2 (PHD2), that contributes to this adaptive response. We show that a variant in EGLN1, c.[12C>G; 380G>C], contributes functionally to the Tibetan high-altitude phenotype. PHD2 triggers the degradation of hypoxia-inducible factors (HIFs), which mediate many physiological responses to hypoxia, including erythropoiesis. The PHD2 p.[Asp4Glu; Cys127Ser] variant exhibits a lower K_m value for oxygen, suggesting that it promotes increased HIF degradation under hypoxic conditions. Whereas hypoxia stimulates the proliferation of wild-type erythroid progenitors, the proliferation of progenitors with the c.[12C>G; 380G>C] mutation in EGLN1 is significantly impaired under hypoxic culture conditions. We show that the c.[12C>G; 380G>C] mutation originated ∼8,000 years ago on the same haplotype previously associated with adaptation to high altitude. The c.[12C>G; 380G>C] mutation abrogates hypoxia-induced and HIF-mediated augmentation of erythropoiesis, which provides a molecular mechanism for the observed protection of Tibetans from polycythemia at high altitude.