Over the past years, much effort has gone towards generating interactions between two optical beams so strong that they could be observed at the level of individual photons1,2,3. Interactions this strong, beyond opening up a new regime in optics4, could lead to technologies such as all-optical quantum information processing5,6. However, the extreme weakness of photon–photon scattering has hindered any attempt to observe such interactions at the level of single particles. Here we present an implementation of a strong optical nonlinearity using electromagnetically induced transparency7, and a direct measurement of the resulting nonlinear phase shift for single post-selected photons. We show that the observed phase shift depends not only on the incident intensity of the (coherent-state) input signal, but also in a discrete fashion on whether 0 or 1 photons are detected at the output. We believe that this constitutes the first direct measurement of the cross-phase shift due to single photons, whose presence or absence is established based on a discrete detection event. It opens a door to future studies of nonlinear optics in the quantum regime, and potential applications in areas such as quantum information processing.