The realization of strong nonlinear interactions between individual light quanta (photons) is a long-standing goal in optical science and engineering, being of both fundamental and technological significance. In conventional optical materials, the nonlinearity at light powers corresponding to single photons is negligibly weak. We demonstrate a medium that is nonlinear at the level of individual quanta, exhibiting strong absorption of photon pairs while remaining transparent to single photons. The quantum nonlinearity is obtained by coherently coupling slowly propagating photons to strongly interacting atomic Rydberg states in a cold, dense atomic gas. Novel non-equilibrium quantum phenomena in such a system, including the realization of strongly correlated many-body states of light, will be discussed.