Oxygen vacancy formation at the (110), (100), (001), and (101) surfaces of rutile TiO2 has been investigated using density functional theory with an on-site correction for strongly correlated systems (DFT+U). In agreement with experimental data, the reduced (110) surface shows an occupied defect state 0.7 eV below the bottom of the conduction band. The other reduced surfaces also show defect states in the band gap, with the defect state energies being strongly dependent on the choice of surface, and following the trend expected from crystal field arguments. For all the reduced surfaces, the excess charge associated with the defect states is primarily localized on two Ti sites neighboring the vacancy, formally reducing these to TiIII. For the (101) and (001) surfaces these Ti sites are geometrically inequivalent, and the corresponding gap states are separated in energy. Vacancy formation energies vary as ΔEvac(100) > ΔEvac(110) > ΔEvac(001) > ΔEvac(101). The variation in vacancy formation energy and gap state energies suggests potential differences between the surfaces in catalytic behavior for adsorbed reactant molecules.