We report on our investigation of structural defect and strain formation in electrodegraded reduced and oxidized, Fe-doped SrTiO3 (Fe:STO) single crystals using optical second harmonic generation (SHG) and confocal Raman spectroscopy. SHG and Raman spectra reveal structural and electrochemical inhomogeneity resulting from the formation of Fe4+/oxygen ion and Fe3+/oxygen vacancy aggregation sites along the degraded anode and cathode interfaces, respectively. We show that mixed Fe3+/Fe4+ states and structural strain gradients are generated across the color fronts. These results, as well as oxygen sublattice differences between the anodic and cathodic bulk, present the color front as an interface between two dominant oxygen bonding distortions. The strain near the color front shows a strong dependence on oxygen vacancy concentration and diffusion within the crystals. Our characterization of structural and electrochemical changes due to electric field-induced strain and oxygen vacancy migration advances knowledge of electrodegradation in perovskite-based titanate single crystals.