By impairing both function and survival, the severe reduction in oxygen availability associated with high-altitude environments is likely to act as an agent of natural selection. We used genomic and candidate gene approaches to search for evidence of such genetic selection. First, a genome-wide allelic differentiation scan (GWADS) comparing indigenous highlanders of the Tibetan Plateau (3,200–3,500 m) with closely related lowland Han revealed a genome-wide significant divergence across eight SNPs located near EPAS1. This gene encodes the transcription factor HIF2α, which stimulates production of red blood cells and thus increases the concentration of hemoglobin in blood. Second, in a separate cohort of Tibetans residing at 4,200 m, we identified 31 EPAS1 SNPs in high linkage disequilibrium that correlated significantly with hemoglobin concentration. The sex-adjusted hemoglobin concentration was, on average, 0.8 g/dL lower in the major allele homozygotes compared with the heterozygotes. These findings were replicated in a third cohort of Tibetans residing at 4,300 m. The alleles associating with lower hemoglobin concentrations were correlated with the signal from the GWADS study and were observed at greatly elevated frequencies in the Tibetan cohorts compared with the Han. High hemoglobin concentrations are a cardinal feature of chronic mountain sickness offering one plausible mechanism for selection. Alternatively, as EPAS1 is pleiotropic in its effects, selection may have operated on some other aspect of the phenotype. Whichever of these explanations is correct, the evidence for genetic selection at the EPAS1 locus from the GWADS study is supported by the replicated studies associating function with the allelic variants.