Previously, we constructed a series of reduced-genome strains of Escherichia coli by combining large-scale chromosome deletions and then tested the sensitivity of these strains to the redox-cycling drug menadione. In this study, we analyzed a deletion that increased menadione sensitivity and discovered that loss of selenocysteine synthase genes was responsible for the strain's reduced tolerance to oxidative stress. Mutants of formate dehydrogenases, which are selenocysteine-containing enzymes, were also sensitive to menadione, indicating that these enzymes are involved in oxidative stress during stationary phase, specifically under microaerobic conditions in the presence of glucose. Among three formate dehydrogenases encoded by the E. coli genome, two were responsible for the observed phenotypes: formate dehydrogenase-H and -O. In a mutant of fdhD, which encodes a sulfur transferase that is essential for formate dehydrogenase activity, formate dehydrogenase-O could still contribute to oxidative stress tolerance, revealing a novel role for this protein. Consistent with this, overproduction of the electron transfer subunits of this enzyme, FdoH and FdoI, increased menadione tolerance and supported survival in stationary phase. These results suggested that formate dehydrogenase-O serves as an electron transfer element in glucose metabolism to promote oxidative stress tolerance and survival in stationary phase.