Geometric and electronic surface reconstructions determine the physical and chemical properties of surfaces and, consequently, their functionality in applications. The reconstruction of a surface minimizes its surface free energy in otherwise thermodynamically unstable situations, typically caused by dangling bonds, lattice stress, or a divergent surface potential, and it is achieved by a cooperative modification of the atomic and electronic structure. Here, we combined first-principles calculations and surface techniques (scanning tunneling microscopy, non-contact atomic force microscopy, scanning tunneling spectroscopy) to report that the repulsion between negatively charged polaronic quasiparticles, formed by the interaction between excess electrons and the lattice phonon field, plays a key role in surface reconstructions. As a paradigmatic example, we explain the (1×1) to (1×2) transition in rutile TiO2(110).