This review focuses on the molecular stratagems utilized by bacteria, yeast, and mammals in their adaptation to hypoxia. Among this broad range of organisms, changes in oxygen tension appear to be sensed by heme proteins, with subsequent transfer of electrons along a signal transduction pathway which may depend on reactive oxygen species. These heme-based sensors are generally two-domain proteins. Some are hemokinases, while others are flavohemoproteins [flavohemoglobins and NAD(P)H oxidases]. Hypoxia-dependent kinase activation of transcription factors in nitrogen-fixing bacteria bears a striking analogy to the phosphorylation of hypoxia inducible factor-1 (HIF-1) in mammalian cells. Moreover, redox chemistry appears to play a critical role both in the trans-activation of oxygen-responsive genes in unicellular organisms as well as in the activation of HIF-1. In yeast and bacteria, regulatory operons coordinate expression of genes responsible for adaptive responses to hypoxia and hyperoxia. Similarly, in mammals, combinatorial interactions of HIF-1 with other identified transcription factors are required for the hypoxic induction of physiologically important genes.