The virulence of many pathogens depends upon their ability to cope with immune-generated nitric oxide (NO·). In Escherichia coli, the major NO· detoxification systems are Hmp, an NO· dioxygenase (NOD), and NorV, an NO· reductase (NOR). It is well established that Hmp is the dominant system under aerobic conditions, whereas NorV dominates anaerobic conditions; however, the quantitative contributions of these systems under the physiologically relevant microaerobic regime remain ill defined. Here, we investigated NO· detoxification in environments ranging from 0 to 50 μM O2, and discovered a regime in which E. coli NO· defenses were severely compromised, as well as conditions that exhibited oscillations in the concentration of NO·. Using an integrated computational and experimental approach, E. coli NO· detoxification was found to be extremely impaired at low O2 due to a combination of its inhibitory effects on NorV, Hmp, and translational activities, whereas oscillations were found to result from a kinetic competition for O2 between Hmp and respiratory cytochromes. Because at least 777 different bacterial species contain the genetic requirements of this stress response oscillator, we hypothesize that such oscillatory behavior could be a widespread phenomenon. In support of this hypothesis,Pseudomonas aeruginosa, whose respiratory and NO· response networks differ considerably from those of E. coli, was found to exhibit analogous oscillations in low O2 environments. This work provides insight into how bacterial NO· defenses function under the low O2 conditions that are likely to be encountered within host environments.