We report measurements of excitation and emission spectra of single, polymer-embedded, perylene dye molecules at room temperature. From these measurements, we can derive the Stokes shift for each single molecule. We determined the distribution of excitation and emission peak energies and, thus, the distribution of single molecule Stokes shifts. Single molecule Stokes shifts have not been recorded to date, and the Stokes shift has often been assumed to be constant in single molecule studies. Our data show that the observed spectral heterogeneity in single molecule emission originates not only from synchronous energetic shifts of the excitation and the emission spectra but also from variations in the Stokes shift, speaking against the assumption of constant Stokes shift.