Modern humans have occupied almost all possible environments globally since exiting Africa about 100,000 years ago. Both behavioral and biological adaptations have contributed to their success in surviving the rigors of climatic extremes, including cold, strong ultraviolet radiation, and high altitude. Among these environmental stresses, high-altitude hypoxia is the only condition in which traditional technology is incapable of mediating its effects. Inhabiting at >3,000-m high plateau, the Tibetan population provides a widely studied example of high-altitude adaptation. Yet, the genetic mechanisms underpinning long-term survival in this environmental extreme remain unknown. We performed an analysis of genome-wide sequence variations in Tibetans. In combination with the reported data, we identified strong signals of selective sweep in two hypoxia-related genes, EPAS1 and EGLN1. For these two genes, Tibetans show unusually high divergence from the non-Tibetan lowlanders (Han Chinese and Japanese) and possess high frequencies of many linked sequence variations as reflected by the Tibetan-specific haplotypes. Further analysis in seven Tibetan populations (1,334 individuals) indicates the prevalence of selective sweep across the Himalayan region. The observed indicators of natural selection on EPAS1 and EGLN1 suggest that during the long-term occupation of high-altitude areas, the functional sequence variations for acquiring biological adaptation to high-altitude hypoxia have been enriched in Tibetan populations.