Hypoxia is a widely occurring condition experienced by diverse organisms under numerous physiological and disease conditions. To probe the molecular mechanisms underlying hypoxia responses and tolerance, we performed a genome-wide screen to identify mutants with enhanced hypoxia tolerance in the model eukaryote, the yeast Saccharomyces cerevisiae . Yeast provides an excellent model for genomic and proteomic studies of hypoxia. We identified five genes whose deletion significantly enhanced hypoxia tolerance. They are RAI1, NSR1, BUD21, RPL20A, and RSM22, all of which encode functions involved in ribosome biogenesis. Further analysis of the deletion mutants showed that they minimized hypoxia-induced changes in polyribosome profiles and protein synthesis. Strikingly, proteomic analysis by using the iTRAQ profiling technology showed that a substantially fewer number of proteins were changed in response to hypoxia in the deletion mutants, compared with the parent strain. Computational analysis of the iTRAQ data indicated that the activities of a group of regulators were regulated by hypoxia in the wild-type parent cells, but such regulation appeared to be diminished in the deletion strains. These results show that the deletion of one of the genes involved in ribosome biogenesis leads to the reversal of hypoxia-induced changes in gene expression and related regulators. They suggest that modifying ribosomal function is an effective mechanism to minimize hypoxia-induced specific protein changes and to confer hypoxia tolerance. These results may have broad implications in understanding hypoxia responses and tolerance in diverse eukaryotes ranging from yeast to humans.