Highland native Andeans have resided at altitude for millennia. They display high aerobic capacity (VO₂max) 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 O₂ sensor that controls levels of the Hypoxia Inducible Factor-α (HIF-α), 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 VO₂max (L⋅min^-1 and mL⋅min^-1⋅kg^-1) in hypoxia (rs1769793, rs2064766, rs2437150, rs2491403, rs479200). For 4 of these SNPs, Quechua had the highest frequency of the advantageous (high VO₂max) allele compared with 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 vs. CC = 30.5 mL⋅min^-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 O₂ delivery or use during exercise at altitude in Peruvian Quechua.