Not yet reviewed by Pith; the record is open.

Rydberg-mediated quantum optics is a useful route toward deterministic quantum information processing based on single photons and quantum networks, but is bottlenecked by the fast motional dephasing of Rydberg atoms. Here, we propose and experimentally demonstrate suppressing the motional dephasing by creating an {\it a priori} unknown but correct phase to each Rydberg atom in an atomic ensemble. The phase created is exactly proportional to the unknown velocity of the thermal motion, resulting in a condition as if no thermal motion occurs to the Rydberg atom upon the retrieval of the signal photon. Our experiments, though hampered by the noise of lasers and the environment, demonstrate more than one order of magnitude enhancement of the coherence time. The feasibility of realizing long-lived storage of single photons in strongly interacting Rydberg media sheds new light on Rydberg-mediated quantum nonlinear optics.