The ability to monitor oxygen (O2) availability and delivery is crucial to an animal's survival. Vertebrates have a number of O2 'sensing' cells that monitor environmental oxygen and ensure adequate delivery to the tissues. While there is little doubt that these cells perform important homeostatic functions, there is little consensus on how a change in O2 concentration, or partial pressure (pO2), is transduced into a physiological response. We recently proposed that the metabolism of hydrogen sulfide (H2S) functions as the O2 sensor in a variety of tissues. In this mechanism, the concentration of biologically active H2S is regulated by the simple balance between constitutive H2S production and its oxidation by mitochondria. This hypothesis is supported by a number of experimental observations in a wide range of O2 sensing tissues: 1) exogenous H2S produces the same physiological response as hypoxia; 2) cellular H2S production is inversely related to pO2 at physiologically relevant pO2s; 3) agonists and antagonists of H2S biosynthesis augment and inhibit hypoxic responses, respectively; and 4) H2S and hypoxia appear to act via common effector pathways. The reciprocal relationship between H2S and O2 also has a long evolutionary history suggesting these gases have been inexorably intertwined throughout evolution. The intent of this review is to elaborate on the mechanism of H2S-mediated O2 sensing.