Atomic ensembles in the form of rare-earth-doped crystals offer significant potential for implementing a quantum memory due to their long coherence lifetimes, enhanced light-matter interaction, and the potential for integration. We use a double Lambda configuration based on hyperfine levels in praseodymium doped yttrium orthosilicate. In this scheme, a probabilistically generated collective excitation of the internal atomic states in the form of a spin-wave is signaled by emission of a Stokes-shifted herald photon via spontaneous Raman scattering. After a storage delay, a read field addresses the appropriate transition, mapping the spin wave back to a photon, resulting in the emission of an anti-Stokes shifted retrieved photon. Momentum conservation, as dictated by phase-matching conditions, ensure that the herald and retrieved photons are emitted in a well-defined spatial modes relative to the co-propagating write and read optical fields. Inhomogeneous broadening of the absorption profile precludes straightforward implementation of the above scheme, and we resort to spectral hole-burning techniques to prepare a sub-ensemble of atoms with a narrow range of optical transition energy in the ground state. Using a second identical crystal, we also implement an optical spectral filter that suppresses the powerful write and read beams, and spontaneous-emission noise, while transmitting the herald and retrieved photons. We report on the second-order optical correlations between the herald and retrieved photons that are the signature of generation and retrieval of a stored spin-wave excitation. Demonstration of such a quantum memory is an enabling step towards distributing entanglement for a quantum repeater scheme.