Strong nonlinearity at the single photon level represents a crucial enabling tool for optical quantum technologies. Here we report on experimental implementation of a strong Kerr nonlinearity by measurement-induced quantum operations on weak quantum states of light. Our scheme coherently combines two sequences of single photon addition and subtraction to induce a nonlinear phase shift at the single photon level. We probe the induced nonlinearity with weak coherent states and characterize the output non-Gaussian states with quantum state tomography. The strong nonlinearity is clearly witnessed as a change of sign of specific off-diagonal density matrix elements in the Fock basis.