We report the storage and retrieval of single photons, via a quantum memory, in the optical phonons of a room-temperature bulk diamond. The THz-bandwidth heralded photons are generated by spontaneous parametric down-conversion and mapped to phonons via a Raman transition, stored for a variable delay, and released on demand. The second-order correlation of the memory output is g((2))(0)=0.65±0.07, demonstrating a preservation of nonclassical photon statistics throughout storage and retrieval. The memory is low noise, high speed and broadly tunable; it therefore promises to be a versatile light-matter interface for local quantum processing applications.