We have studied the electronic structure and charge ordering (Verwey) transition of magnetite (Fe3O4) by soft x-ray photoemission. Due to the enhanced probing depth and the use of different surface preparations we are able to distinguish surface and volume effects in the spectra. The pseudogap behavior of the intrinsic spectra and its temperature dependence give evidence for the existence of strongly bound small polarons consistent with both dc and optical conductivity. Together with other recent structural and theoretical results our findings support a picture in which the Verwey transition contains elements of a cooperative Jahn-Teller effect, stabilized by local Coulomb interaction.