The ability to withstand low oxygen (hypoxia tolerance) is a polygenic and mechanistically conserved trait that has important implications for both human health and evolution. However, little is known about the diversity of genetic mechanisms involved in hypoxia adaptation in evolving populations. We used experimental evolution and whole-genome sequencing in Drosophila melanogaster to investigate the role of natural variation in adaptation to hypoxia. Using a generalized linear mixed model we identified significant allele frequency differences between three independently evolved hypoxia-tolerant populations and normoxic control populations for approximately 3,800 single nucleotide polymorphisms. Around 50% of these variants are clustered in 66 distinct genomic regions. These regions contain genes that are differentially expressed between hypoxia-tolerant and normoxic populations and several of the differentially expressed genes are associated with metabolic processes. Additional genes associated with respiratory and open tracheal system development also show evidence of directional selection. RNAi-mediated knockdown of several candidate genes’ expression significantly enhanced survival in severe hypoxia. Using genomewide single nucleotide polymorphism data from four high-altitude human populations—Sherpas, Tibetans, Ethiopians, and Andeans, we found that several human orthologs of the genes under selection in flies are also likely under positive selection in all four high-altitude human populations. Thus, our results indicate that selection for hypoxia tolerance can act on standing genetic variation in similar genes and pathways present in organisms diverged by hundreds of millions of years.