Nitric oxide (NO) detoxification enzymes, such as NO dioxygenase (NOD) and NO reductase (NOR), are important to the virulence of numerous bacteria. Pathogens use these defense systems to ward off immune-generated NO, and they do so in environments that contain additional stressors, such as reactive oxygen species, nutrient deprivation, and acid stress. NOD and NOR both use reducing equivalents to metabolically deactivate NO, which suggests that nutrient deprivation could negatively impact their functionality. To explore the relationship between NO detoxification and nutrient deprivation, we examined the ability of Escherichia coli to detoxify NO under different levels of carbon source availability in aerobic cultures. We observed failure of NO detoxification under both carbon source limitation and starvation, and those failures could have arisen from inabilities to synthesize Hmp (NOD of E. coli) and/or supply it with sufficient NADH (preferred electron donor). We found that when limited quantities of carbon source were provided, NO detoxification failed due to insufficient NADH, whereas starvation prevented Hmp synthesis, which enabled cells to maintain their NADH levels. This maintenance of NADH levels under starvation was confirmed to be dependent on the absence of Hmp. Intriguingly, these data show that under NO stress, carbon-starved E. coli are better positioned with regard to reducing power to cope with other stresses than cells that had consumed an exhaustible amount of carbon.