When oxygen becomes limiting, denitrifying bacteria must prepare for anaerobic respiration by synthesizing the reductases NAR (NO3− → NO2−), NIR (NO2− → NO), NOR (2NO → N2O), and NOS (N2O → N2), either en bloc or sequentially, to avoid entrapment in anoxia without energy. Minimizing the metabolic burden of this precaution is a plausible fitness trait, and we show that the model denitrifier Paracoccus denitrificans achieves this by synthesizing NOS in all cells, while only a minority synthesize NIR. Phenotypic diversification with regards to NIR is ascribed to stochastic initiation of gene transcription, which becomes autocatalytic via NO production. Observed gas kinetics suggest that such bet hedging is widespread among denitrifying bacteria. Moreover, in response to oxygenation, P. denitrificans preserves NIR in the poles of nongrowing persister cells, ready to switch to anaerobic respiration in response to sudden anoxia. Our findings add dimensions to the regulatory biology of denitrification and identify regulatory traits that decrease N2O emissions.