Antibiotics are a critical element of modern health care that is threatened by the microbes’ natural propensity to evolve resistance. Experimental evolution of antimicrobial resistance (AMR) is a powerful in vitro approach that enables precise control over culture conditions and direct observation of mutational trajectories towards resistance. However, experimental evolution studies have historically overlooked the ecological context of AMR evolution in the natural world; many of the environments in which microbes are naturally selected by antibiotics are oxygen-limited. Notably, the microbially diverse human gut is largely anaerobic, and can serve as both a crucible and a reservoir for antibiotic-resistant pathogens. To systematically address this gap in understanding of how oxygen impacts the de novo evolution of AMR, we experimentally evolved clinical isolate strains of E. coli towards resistance in either aerobic or anaerobic conditions. Cultures were serially passaged across dynamically tuned antibiotic gradients, which tracked the increasing resistance of independent lineages over time. We discover that oxygen generally leads to higher AMR evolution, whereby average fold-change in phenotypic resistance (end/start of evolutionary campaign) is significantly different between atmospheric conditions for gentamicin, tetracycline, and cefoxitin, but not for ciprofloxacin. Whole genome sequencing of the evolved lineages demonstrates that certain high-frequency, AMR-associated mutations may have oxygen-dependent fitness tradeoffs. For gentamicin resistance, central bioenergetic machinery, cytochrome bd oxidase and ATP synthase, are specifically mutated in aerobic and anaerobic conditions, respectively. This suggests that the microbial environment can constrain and modulate evolutionary trajectories to resistance due to its effects on the mutational landscapes of key antibiotic resistance genes. By unraveling the eco-evolutionary principles that underly antimicrobial resistance, we stand to discover novel strategies and targets to ultimately control the lethal emergence of AMR.