Separating oxygen from air to create oxygen-enriched gas streams is a process that is significant in both industrial and medical fields. However, the prominent technologies for creating oxygen-enriched gas streams are both energy and infrastructure intensive as they use cryogenic temperatures or materials that adsorb N2 from air. The latter method is less efficient than the methods that adsorb O2 directly. Herein, we show, via a combination of gas adsorption isotherms, gas breakthrough experiments, neutron and synchrotron X-ray powder diffraction, Raman spectroscopy, and computational studies, that the metal–organic framework, Al(HCOO)3 (ALF), which is easily prepared at low cost from commodity chemicals, exhibits substantial O2 adsorption and excellent time-dependent O2/N2 selectivity in a range of 50–125 near dry ice/solvent (≈190 K) temperatures. The effective O2 adsorption with ALF at ≈190 K and ≈0.21 bar (the partial pressure of O2 in air) is ≈1.7 mmol/g, and at ice/salt temperatures (≈250 K), it is ≈0.3 mmol/g. Though the kinetics for full adsorption of O2 near 190 K are slower than at temperatures nearer 250 K, the kinetics for initial O2 adsorption are fast, suggesting that O2 separation using ALF with rapid temperature swings at ambient pressures is a potentially viable choice for low-cost air separation applications. We also present synthetic strategies for improving the kinetics of this family of compounds, namely, via Al/Fe solid solutions. To the best of our knowledge, ALF has the highest O2/N2 sorption selectivity among MOF adsorbents without open metal sites as verified by co-adsorption experiments.