The realization of strong nonlinear interactions between individual light quanta (photons) is a long-standing goal in optical science and engineering(1,2), being of both fundamental and technological significance. In conventional optical materials, the nonlinearity at light powers corresponding to single photons is negligibly weak. Here 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(3-5) to strongly interacting atomic Rydberg states(6-12) in a cold, dense atomic gas(13,14). Our approach paves the way for quantum-byquantum control of light fields, including single-photon switching(15), all-optical deterministic quantum logic(16) and the realization of strongly correlated many-body states of light(17).