Oxygen availability is the major determinant of the metabolic modes adopted by Escherichia coli. Although much is known about E. coli gene expression and metabolism under fully aerobic and anaerobic conditions, the intermediate oxygen tensions that are encountered in natural niches are understudied. Here, for the first time, the transcript profiles of E. coli K-12 across the physiologically significant range of oxygen availabilities are described. These suggested a progressive switch to aerobic respiratory metabolism and a remodeling of the cell envelope as oxygen availability increased. The transcriptional responses were consistent with changes in the abundance of cytochrome bd and bo' and the outer membrane protein OmpW. The observed transcript and protein profiles result from changes in the activities of regulators that respond to oxygen itself or to metabolic and environmental signals that are sensitive to oxygen availability (aerobiosis). A probabilistic model (TFInfer) was used to predict the activity of the indirect oxygen-sensing two-component system ArcBA across the aerobiosis range. The model implied that the activity of the regulator ArcA correlated with aerobiosis but not with the redox state of the ubiquinone pool, challenging the idea that ArcA activity is inhibited by oxidized ubiquinone. The amount of phosphorylated ArcA correlated with the predicted ArcA activities and with aerobiosis, suggesting that fermentation product-mediated inhibition of ArcB phosphatase activity is the dominant mechanism for regulating ArcA activity under the conditions used here.