We report a high fidelity optical memory in which dynamical decoupling is used to extend the storage time. This is demonstrated in a rare-earth doped crystal in which optical coherences were transferred to nuclear spin coherences and then protected against environmental noise by dynamical decoupling, leading to storage times of up to 4.2 ms. An interference experiment shows that relative phases of input pulses are preserved through the whole storage and retrieval process with a visibility ≈1, demonstrating the usefulness of dynamical decoupling for extending the storage time of quantum memories. We also show that dynamical decoupling sequences insensitive to initial spin coherence increase retrieval efficiency.