The budding yeast Saccharomyces cerevisiae is a facultative aerobe that responds to changes in oxygen availability (and carbon source) by initiating a biochemically complex program that ensures that energy demands are met under two different physiological states: aerobic growth, supported by oxidative and fermentative pathways, and anaerobic growth, supported solely by fermentative processes. This program includes the differential expression of a large number of genes, many of which are involved in the direct utilization of oxygen. Research over the past decade has defined many of the cis-sites and trans-acting factors that control the transcription of these oxygen-responsive genes. However, the manner in which oxygen is sensed and the subsequent steps involved in the transduction of this signal have not been precisely determined. Heme is known to play a pivotal role in the expression of these genes, acting as a positive modulator for the transcription of the aerobic genes and as a negative modulator for the transcription of the hypoxic genes. Consequently, cellular concentrations of heme, whose biosynthesis is oxygen-dependent, are thought to provide a gauge of oxygen availability and dictate which set of genes will be transcribed. But the precise role of heme in oxygen sensing and the transcriptional regulation of oxygen-responsive genes is presently unclear. Here, we provide an overview of the transcriptional regulation of oxygen-responsive genes, address the functional roles that heme and hemoproteins may play in this regulation, and discuss possible mechanisms of oxygen sensing in this simple eukaryotic organism.