Highland native Andeans have resided at altitude for millennia. They display high aerobic capacity (VO_2max) at altitude and this may be a reflection of genetic adaptation to chronic hypoxia. Previous genome-wide (GW) scans for natural selection have nominated EGLN1 as a candidate gene. The encoded protein, EGLN1/PHD2, is an O₂ sensor that controls levels of the Hypoxia Inducible Factor-a (HIF-a), which regulates the cellular response to hypoxia. From GWAS and ANCOVA performed on a total sample that included n=429 Peruvian Quechua and n=94 US lowland referents, we identified five EGLN1 SNPs associated with higher VO₂max (l^.min^-1 and ml^.min^-1.kg^-1) in hypoxia (rs1769793, rs2064766, rs2437150, rs2491403, rs479200). For four of these SNPs, Quechua had the highest frequency of the advantageous (high VO₂max) allele compared to 25 diverse lowland comparison populations from the 1000 Genomes project. Genotype effects were substantial with high versus low VO₂max genotype categories differing by ~11% (e.g., for rs1769793 SNP genotype TT=34.2 ml^.min^-1.kg^-1 versus CC=30.5 ml^.min^-1.kg^-1). To guard against spurious association, we controlled for population stratification. Also, 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 O₂ delivery or use during exercise at altitude in Peruvian Quechua.