We report the 3.3 Å resolution structure of dimeric membrane-bound O2-tolerant hydrogenase 1 from Escherichia coli in a 2:1 complex with its physiological partner, cytochrome b. From the short distance between distal [Fe4S4] clusters, we predict rapid transfer of H2-derived electrons between hydrogenase heterodimers. Thus, under low O2 levels, a functional active site in one heterodimer can reductively reactivate its O2-exposed counterpart in the other. Hydrogenase 1 is maximally expressed during fermentation, when electron acceptors are scarce. These conditions are achieved in the lower part of the host's intestinal tract when E. coli is soon to be excreted and undergo an anaerobic-to-aerobic metabolic transition. The apparent paradox of having an O2-tolerant hydrogenase expressed under anoxia makes sense if the enzyme functions to keep intracellular O2 levels low by reducing it to water, protecting O2-sensitive enzymes during the transition. Cytochrome b's main role may be anchoring the hydrogenase to the membrane.