The temperature dependence of the electronic and atomic structure of the colossal magnetoresistive oxides La1-xSrxMnO3 (x=0.3, 0.4) has been studied using core and valence level photoemission, x-ray absorption and emission, and extended x-ray absorption fine structure spectroscopy. A dramatic and reversible change of the electronic structure is observed on crossing the Curie temperature, including charge localization on and spin-moment increase of Mn, together with Jahn-Teller distortions, both signatures of polaron formation. Our data are also consistent with a phase-separation scenario.