Large nonlinearity at the single-photon level can pave the way for the implementation of universal quantum gates. However, realizing large and noiseless nonlinearity at such low light levels has been a great challenge for scientists in the past decade. Here, we propose a scheme that enables substantial nonlinear interaction between two light fields that are both stored in an atomic memory. Semiclassical and quantum simulations demonstrate the feasibility of achieving large cross-phase modulation (XPM) down to the single-photon level. The proposed scheme can be used to implement parity gates from which CNOT gates can be constructed. Furthermore, we present a proof of principle experimental demonstration of XPM between two optical pulses: one stored and one freely propagating through the memory medium.