Surfaces of rutile-like RuO2, especially the most stable (110) surface, are important for catalysis, sensing and charge storage applications. Structure, chemical composition, and properties of the surface depend on external conditions. Using the evolutionary prediction method USPEX, we found stable reconstructions of the (110) surface. Two stable reconstructions, RuO4-(2 × 1) and RuO2-(1 × 1), were found, and the surface phase diagram was determined. The new RuO4-(2 × 1) reconstruction is stable in a wide range of environmental conditions, its simulated STM image perfectly matches experimental data, it is more thermodynamically stable than previously proposed reconstructions, and explains well pseudocapacitance of RuO2 cathodes.