Despite many prior studies on microbial response to oxidative stress, our understanding of microbial tolerance against oxidative stress is currently limited to aerobic conditions, and few engineering strategies have been devised to resolve toxicity issues of oxidative stress under anaerobic conditions. Since biological processes, such as anaerobic fermentation, are frequently hampered by toxicity arising from oxidative stress, increased microbial tolerance against oxidative stress improves the overall productivity and yield of biological processes. Here, we show a systems-level analysis of oxidative stress response of Escherichia coli under anaerobic conditions, and present an engineering strategy to improve oxidative stress tolerance. First, we identified essential cellular mechanisms and regulatory factors underlying oxidative stress response under anaerobic conditions using a transcriptome analysis. In particular, we showed that nitrogen metabolisms and respiratory pathways were differentially regulated in response to oxidative stress under anaerobic and aerobic conditions. Further, we demonstrated that among transcription factors with oxidative stress-derived perturbed activity, the deletion of arcA and arcB significantly improved oxidative stress tolerance under aerobic and anaerobic conditions, respectively, whereas fnr was identified as an essential transcription factor for oxidative stress tolerance under anaerobic conditions. Moreover, we showed that oxidative stress increased the intracellular NADH : NAD(+) ratio under aerobic and anaerobic conditions, which indicates a regulatory role of NADH in oxidative stress tolerance. Based on this finding, we demonstrated that increased NADH availability through fdh1 overexpression significantly improved oxidative stress tolerance under aerobic conditions. Our results here provide novel insight into better understanding of cellular mechanisms underlying oxidative stress tolerance under anaerobic conditions, and into developing strain engineering strategies to enhance microbial tolerance against oxidative stress towards improved biological processes.