Rutile TiO2 is the most stable phase of this important mineral, which is a promising photocatalyst used for the remediation of pollutants, and photoelectron chemical conversion of solar energy. Therein, surfaces play the key role in photochemical reactions. The Wulff construction of rutile TiO2 predicts a tetragonal prism bounded by{110} surfaces and terminated by a pair of tetragonal pyramids bounded by{011} surfaces. However, atomic structures of these surfaces are uncertain, which hamper understanding related reaction mechanisms. Firstly, reconstructions of rutile TiO2(110) surface were investigated using the evolutionary approach. Depending on thermodynamic conditions, four different structures have been observed for this surface. We confirm the recently proposed ‘Ti2O3-(1×2)’ and ‘Ti2O-(1×2)’ reconstructions, and predict two new reconstructions ‘Ti3O2-(1×2)’ and ‘Ti3O3-(2×1)’, which match experimental results. Furthermore, we find that surface electronic states are sensitive to reconstruction and therefore depend on thermodynamic conditions: deep donor energy levels associated with the surface, significantly reduce band gaps and may allow absorption of visible light. Secondly, reconstructions of rutile TiO2(011) were also investigated. It is found that reconstructions mainly depend on the changes of chemical potential, indicating that thermodynamics conditions determine reconstructions. More importantly, uncertainties are resolved, and new reconstructions are predicted. Firstly, our investigation reveals that ‘Titanyl-TiO2’ and ‘Titanyl-Ti2O3’ reconstructions could be used for rationalizing previous experimental findings. Secondly, the predicted ‘MF(111)-TiO’ reconstruction is more desirable than the previously proposed ‘MF(111)-TiO3’ model. Thirdly, ‘MF(110)-TiO’ and ‘MR-TiO’ reconstructions are predicted to be stable in ultrahigh vacuum at higher temperature. Furthermore, band gaps of reconstructed structures are significantly reduced, which enhances the absorption of visible light.