We report the solution of the c(4 x 2) reconstruction of SrTiO3 (001), obtained through a combination of high-resolution transmission electron microscopy, direct methods analysis, and density functional theory. The structure is characterized by a single overlayer of TiO2 stoichiometry in which TiO5 polyhedra are arranged into edge-shared structures, in contrast to the corner-shared TiO6 polyhedra in bulk. This structural pattern is similar to that reported by us earlier for the (2 x 1) reconstruction of the same crystal face formed at higher temperature. We discuss probable mechanisms of surface stabilization as revealed by these two solutions which are likely to apply to other reconstructions of SrTiO3 (001) and, possibly, other perovskites in general.