Reconstructions of the (110) surface of rutile TiO2 (the dominant surface of this important mineral and catalyst) are investigated using the evolutionary approach, resolving previous controversies. Depending on thermodynamic conditions, four different stable reconstructions are 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 reconstructions and, therefore, depend on thermodynamic conditions.