We present an analytical theory for the nonlinear optical response of a strongly interacting Rydberg gas under conditions of electromagnetically induced transparency. Simple formulae for the third order optical susceptibility are derived and shown to be in excellent agreement with recent experiments. The obtained expressions reveal strong nonlinearities, which in addition are of highly nonlocal character. This property together with enormous strength of the Rydberg-induced nonlinearities is shown to yield a unique laboratory platform for nonlinear wave phenomena, such as collapse-arrested modulational instabilities in a self-defocussing medium.