The air-free reaction of CoCl2 with 1,3,5-tri(1H-1,2,3-triazol-5-yl)benzene (H3BTTri) in N,N-dimethylformamide (DMF) and methanol leads to the formation of Co-BTTri (Co3[(Co4Cl)3(BTTri)8]2·DMF), a sodalite-type metal-organic framework. Desolvation of this material generates coordinatively unsaturated low-spin cobalt(II) centers that exhibit a strong preference for binding O2 over N2, with isosteric heats of adsorption (Qst) of -34(1) and -12(1) kJ/mol, respectively. The low-spin (S = 1/2) electronic configuration of the metal centers in the desolvated framework is supported by structural, magnetic susceptibility, and computational studies. A single-crystal X-ray structure determination reveals that O2 binds end-on to each framework cobalt center in a 1:1 ratio with a Co-O2 bond distance of 1.973(6) Å. Replacement of one of the triazolate linkers with a more electron-donating pyrazolate group leads to the isostructural framework Co-BDTriP (Co3[(Co4Cl)3(BDTriP)8]2·DMF; H3BDTriP = 5,5'-(5-(1H-pyrazol-4-yl)-1,3-phenylene)bis(1H-1,2,3-triazole)), which demonstrates markedly higher yet still fully reversible O2 affinities (Qst = -47(1) kJ/mol at low loadings). Electronic structure calculations suggest that the O2 adducts in Co-BTTri are best described as cobalt(II)-dioxygen species with partial electron transfer, while the stronger binding sites in Co-BDTriP form cobalt(III)-superoxo moieties. The stability, selectivity, and high O2 adsorption capacity of these materials render them promising new adsorbents for air separation processes.