In addition to composition, the structure of a catalyst is another fundamental determinant of its catalytic reactivity. Recently, anomalous Ti oxide-rich surface phases of ternary oxides have been stabilized as nonstoichiometric epitaxial overlayers. These structures give rise to different modes of oxygen binding, which may lead to different oxidative chemistry. Through density functional theory investigations and electrochemical measurements, we predict and subsequently show that such a TiO2 double-layer surface reconstruction enhances the oxygen evolving activity of the perovskite-type oxide SrTiO3. Our theoretical work suggests that the improved activity of the restructured TiO2(001) surface toward oxygen formation stems from (i) having two Ti sites with distinct oxidation activity and (ii) being able to form a strong O-O moiety (which reduces overbonding at Ti sites), which is a direct consequence of (iii) having a labile lattice O that is able to directly participate in the reaction. Here, we demonstrate the improvement of the catalytic performance of a well-known and well-studied oxide catalyst through more modern methods of materials processing, predicted through first-principles theoretical modeling.