We have studied the O 2p valence-band structure of Nb-doped SrTiO3, in which a dilute concentration of electrons are doped into the d0 band insulator, by angle-resolved photoemission spectroscopy (ARPES) measurements. We found that ARPES spectra at the valence band maxima at the M [k = (pi/a, pi/a, 0)]and R [k = (pi/a, pi/a, pi/a)] points start from ~ 3.3 eV below the Fermi level (EF), consistent with the indirect band gap of 3.3 eV and the EF position at the bottom of the conduction band. The peak position of the ARPES spectra were, however, shifted toward higher binding energies by ~ 500 meV from the 3.3 eV threshold. Because the bands at M and R have pure O 2p character, we attribute this ~ 500 meV shift to strong coupling of the oxygen p hole with optical phonons in analogy with the peak shifts observed for d-electron photoemission spectra in various transition-metal oxides.