A major goal of energy research is to use visible light to cleave water directly, without an applied voltage, into hydrogen and oxygen. Although SrTiO3 requires ultraviolet light, after four decades, it is still the "gold standard" for the photo-catalytic splitting of water. It is chemically robust and can carry out both hydrogen and oxygen evolution reactions without an applied bias. While ultrahigh vacuum surface science techniques have provided useful insights, we still know relatively little about the structure of these electrodes in contact with electrolytes under operating conditions. Here, we report the surface structure evolution of a n-SrTiO3 electrode during water splitting, before and after "training" with an applied positive bias. Operando high-energy X-ray reflectivity measurements demonstrate that training the electrode irreversibly reorders the surface. Scanning electrochemical microscopy at open circuit correlates this training with a 3-fold increase of the activity toward the photo-induced water splitting. A novel first-principles joint density functional theory simulation, constrained to the X-ray data via a generalized penalty function, identifies an anatase-like structure as the more active, trained surface.