Colonization of the gastrointestinal tract by Escherichia coli is dependent upon its ability to compete with the commensal microflora. We have established that nutrient acquisition is important for competition and fitness of E. coli strains in the mammalian intestine. However, the importance of respiration and the respiratory pathways used by E. coli for colonization was unknown prior to this study. We used a systematic mutational approach to test the hypothesis that respiratory metabolism is important for E. coli to colonize the mouse intestine. We found that a strain lacking cytochrome bo3 oxidase (cyoAB) co-colonized with the wild-type. A mutant lacking the high oxygen affinity terminal cytochrome bd oxidase (cydAB and cydDC) failed to initiate and could not colonize. Of the four anaerobic respiratory pathways, dimethylsulfoxide (DMSO) reductase (dmsAB), trimethylamine-N-oxide (TMAO) reductase (torCA), and nitrite reductase (nirBD) were found to be unimportant, while nitrate reductase (narG, narZ, and napDA) and fumarate reductase (frdA) mutants were able to initiate colonization but showed major defects in maintenance. Our findings lead us to conclude that respiration of oxygen provides a competitive advantage to E. coli in vivo despite the low availability of its preferred carbon sources. E. coli also requires use of alternative anaerobic electron acceptors, such as nitrate and fumarate, to be competitive in the intestine. Furthermore, respiratory flexibility allows E. coli to maximize its colonization efficiency to ensure its success in the mammalian gastrointestinal tract. The experiments described in this study suggest that facultative anaerobes may make the intestinal environment more anaerobic, thereby promoting the stability of the predominantly anaerobic microflora. Indeed, the intestinal environment is likely microaerobic, oxygen tension almost certainly fluctuates in the intestine. These experiments provide the first evidence for an aerobic microhabitat in the intestine and suggest a hierarchy of alternative electron acceptors support colonization. Additionally, the results show that energy storage in the form of glycogen may also be important during times of nutrient limitation to enhance persistence of E. coli in the intestine.