Baker's yeast, Saccharomyces cerevisiae, can adapt to growth under severe oxygen limitation. Two regulatory systems are described here that control this adaptation. The first involves a heme-dependent repression mechanism. Cells sense hypoxia through the inability to maintain oxygen-dependent heme biosynthesis. Under aerobic conditions, heme accumulates and serves as an effector for the transcriptional activator Hap1. The heme-Hap1 complex activates transcription of the ROX1 gene that encodes a repressor of one set of hypoxic genes. Under hypoxic conditions, heme levels fall, and a heme-deficient Hap1 complex represses ROX1 expression. As a consequence, the hypoxic genes are derepressed. The second regulatory system activates gene expression in response to a variety of stress conditions, including oxygen limitation. Oxygen sensing in this system is heme-independent. The same DNA sequence mediates transcriptional activation of each stress signal.