Highland native Andeans have resided at altitude for millennia. They display high aerobic capacity (VO2max) at altitude, which may be a reflection of genetic adaptation to hypoxia. Previous genomewide (GW) scans for natural selection have nominated Egl-9 homolog 1 gene (EGLN1) as a candidate gene. The encoded protein, EGLN1/PHD2, is an O2 sensor that controls levels of the Hypoxia Inducible Factor-alpha (HIF-alpha), which regulates the cellular response to hypoxia. From GW association and analysis of covariance performed on a total sample of 429 Peruvian Quechua and 94 US lowland referents, we identified 5 EGLN1 SNPs associated with higher VO2max (Lmin(-1) and mLmin(-1)kg(-1)) in hypoxia (rs1769793, rs2064766, rs2437150, rs2491403, rs479200). For 4 of these SNPs, Quechua had the highest frequency of the advantageous (high VO2max) allele compared with 25 diverse lowland comparison populations from the 1000 Genomes Project. Genotype effects were substantial, with high versus low VO2max genotype categories differing by approximately 11% (e.g., for rs1769793 SNP genotype TT = 34.2 mLmin(-1)kg(-1) vs. CC = 30.5 mLmin(-1)kg(-1)). To guard against spurious association, we controlled for population stratification. Findings were replicated for EGLN1 SNP rs1769793 in an independent Andean sample collected in 2002. These findings contextualize previous reports of natural selection at EGLN1 in Andeans, and support the hypothesis that natural selection has increased the frequency of an EGLN1 causal variant that enhances O2 delivery or use during exercise at altitude in Peruvian Quechua.