In this paper, we propose a new adsorption model for molecular oxygen on reduced TiO2(110), based on extensive first principles density functional calculations. For the first time, our calculations predict formation of tetraoxygen (O4) anchored at the vacancy site, which in turn allows adsorption of three O2 molecules per vacancy in saturation coverage. We present the structure, bonding, and energetics of adsorbed oxygen species by changing the number of adsorbed oxygen molecules per vacancy. We also find that thermally activated O2 desorption may take place via two channels that require overcoming barriers of 0.41 and 1.25 eV, respectively. In addition, our study provides strong theoretical evidence for the change in O2 reactivity with O2 coverage. Our findings associated with tetraoxygen complexes are consistent with existing experimental results.