Molecular oxygen (O2) and nitric oxide (NO) are diatomic gases that play major roles in infection. The host innate immune system generates reactive oxygen species and NO as bacteriocidal agents and both require O2 for their production. Furthermore, the ability to adapt to changes in O2 availability is crucial for many bacterial pathogens, as many niches within a host are hypoxic. Pathogenic bacteria have evolved transcriptional regulatory systems that perceive these gases and respond by reprogramming gene expression. Direct sensors possess iron-containing co-factors (iron-sulfur clusters, mononuclear iron, heme) or reactive cysteine thiols that react with O2 and/or NO. Indirect sensors perceive the physiological effects of O2 starvation. Thus, O2 and NO act as environmental cues that trigger the coordinated expression of virulence genes and metabolic adaptations necessary for survival within a host. Here, the mechanisms of signal perception by key O2- and NO-responsive bacterial transcription factors and the effects on virulence gene expression are reviewed, followed by consideration of these aspects of gene regulation in two major pathogens, Staphylococcus aureus and Mycobacterium tuberculosis.