The properties of reduced rutile TiO2(110) surfaces, as well as the adsorption, diffusion, and dissociation of molecular oxygen are investigated by means of density functional theory. The O-2 molecule is found to bind strongly to bridging oxygen vacancies, attaining a molecular state with an expanded O-O bond of 1.44 Angstrom. The molecular oxygen also binds (with somewhat shortened bond lengths) to the fivefold coordinated Ti atoms in the troughs between the bridging oxygen rows, but only when vacancies are present somewhere in the surface. In all cases, the magnetic moment of O-2 is lost upon adsorption. The expanded bond lengths reveal together with inspection of electron density and electronic density of state plots that charging of the adsorbed molecular oxygen is of key importance in forming the adsorption bond. The processes of O-2 diffusion from a vacancy to a trough and O-2 dissociation at a vacancy are both hindered by relative large barriers. However, we find that the presence of neighboring vacancies can strongly affect the ability of O-2 to dissociate. The implications of this in connection with diffusion of the bridging oxygen vacancies are discussed. (C) 2004 American Institute of Physics.