The surfaces of metal oxides often are reconstructed with a geometry and composition that is considerably different from a simple termination of the bulk. Such structures can also be viewed as ultrathin films, epitaxed on a substrate. Here, the reconstructions of the SrTiO3 (110) surface are studied combining scanning tunneling microscopy, transmission electron diffraction, and X-ray absorption spectroscopy, and analyzed with density functional theory calculations. While SrTiO3 (110) invariably terminates with an overlayer of titania, with increasing density its structure switches from nx1 and 2xn. At the same time the coordination of the Ti atoms changes from a network of corner-sharing tetrahedra to a double layer of edge-shared octahedra with bridging units of octahedrally coordinated strontium. This transition from the nx1 to 2xn reconstructions is a transition from a pseudomorphically stabilized tetrahedral network towards an octahedral titania thin film with stress-relief from octahedral strontia units at the surface.