The combination of electromagnetically induced transparency with the nonlinear interaction between Rydberg atoms provides an effective interaction between photons. In this Letter, we investigate the storage of optical pulses as collective Rydberg atomic excitations in a cold atomic ensemble. By measuring the dynamics of the stored Rydberg polaritons, we experimentally demonstrate that storing a probe pulse as Rydberg polaritons strongly enhances the Rydberg mediated interaction compared to the slow propagation case. We show that the process is characterized by two time scales. At short storage times, we observe a strong enhancement of the interaction due to the reduction of the Rydberg polariton group velocity down to 0. For longer storage times, we observe a further, weaker enhancement dominated by Rydberg induced dephasing of the multiparticle components of the state. In this regime, we observe a nonlinear dependence of the Rydberg polariton coherence time with the input photon number. Our results have direct consequences in Rydberg quantum optics and may enable the test of new theories of strongly interacting Rydberg systems.