The ability to sense and adapt to changes in pO2 is crucial for basic metabolism in most organisms, leading to elaborate pathways for sensing hypoxia (low pO2). This review focuses on the mechanisms utilized by mammals and bacteria to sense hypoxia. While responses to acute hypoxia in mammalian tissues lead to altered vascular tension, the molecular mechanism of signal transduction is not well understood. In contrast, chronic hypoxia evokes cellular responses that lead to transcriptional changes mediated by the hypoxia inducible factor (HIF), which is directly controlled by post-translational hydroxylation of HIF by the non-heme Fe(II)/αKG-dependent enzymes FIH and PHD2. Research on PHD2 and FIH is focused on developing inhibitors and understanding the links between HIF binding and the O2 reaction in these enzymes. Sulfur speciation is a putative mechanism for acute O2-sensing, with special focus on the role of H2S. This sulfur-centered model is discussed, as are some of the directions for further refinement of this model. In contrast to mammals, bacterial O2-sensing relies on protein cofactors that either bind O2 or oxidatively decompose. The sensing modality for bacterial O2-sensors is either via altered DNA binding affinity of the sensory protein, or else due to the actions of a two-component signaling cascade. Emerging data suggests that proteins containing a hemerythrin-domain, such as FBXL5, may serve to connect iron sensing to O2-sensing in both bacteria and humans. As specific molecular machinery becomes identified, these hypoxia sensing pathways present therapeutic targets for diseases including ischemia, cancer, or bacterial infection.