The generation and distribution of quantum correlations between photonic qubits is a key resource in quantum information science. For applications in quantum networks and quantum repeaters, it is required that these quantum correlations be stored in a quantum memory. In 2001, Duan, Lukin, Cirac, and Zoller (DLCZ) proposed a scheme combining a correlated photon-pair source and a quantum memory in atomic gases, which has enabled fast progress towards elementary quantum networks. In this Letter, we demonstrate a solid-state source of correlated photon pairs with embedded spin-wave quantum memory, using a rare-earth-ion-doped crystal. We show strong quantum correlations between the photons, high enough for performing quantum communication. Unlike the original DLCZ proposal, our scheme is inherently multimode thanks to a built-in rephasing mechanism, allowing us to demonstrate storage of 11 temporal modes. These results represent an important step towards the realization of complex quantum networks architectures using solid-state resources.