Gas phase complexes formed between bromide and iodide anions and molecular oxygen are investigated via high level CCSD(T) calculations and experimental anion photoelectron spectroscopy. Experimental electron binding energies of the 2P3/2 and 2P1/2 states are determined to be 3.43 and 3.90 eV, and 3.12 and 4.06 eV for the bromide and iodide complexes respectively. Calculations predict one minimum for each of the halide-oxygen complexes corresponding to a bent *Cs geometry, while for the analogous neutral (radical) complexes two stationary points were located; one linear (C$\infty$v) and another T-shaped (C2v). These lie close in energy to one another ($\Delta$E < 1 kJ mol−1) suggesting that internal rotation of the oxygen molecule is highly likely.