Molecular oxygen (O(2)) is the second most abundant gas in the Earth's atmosphere, but in many natural environments, its concentration is reduced to low or even undetectable levels. Although low-oxygen-adapted organisms define the ecology of low-oxygen environments, their capabilities are not fully known. These capabilities also provide a framework for reconstructing a critical period in the history of life, because low, but not negligible, atmospheric oxygen levels could have persisted before the "Great Oxidation" of the Earth's surface about 2.3 to 2.4 billion years ago. Here, we show that Escherichia coli K-12, chosen for its well-understood biochemistry, rapid growth rate, and low-oxygen-affinity terminal oxidase, grows at oxygen levels of ≤ 3 nM, two to three orders of magnitude lower than previously observed for aerobes. Our study expands both the environmental range and temporal history of aerobic organisms.