Interfacing a single photon with another quantum system is a key capability in modern quantum information science. It allows quantum states of matter, such as spin states of atoms1,2, atomic ensembles3,4or solids5, to be prepared and manipulated by photon counting and, in particular, to be distributed over long distances. Such light-matter interfaces have become crucial to fundamental tests of quantum physics6and realizations of quantum networks7. Here we report non-classical correlations between single photons and phonons—the quanta of mechanical motion—from a nanomechanical resonator. We implement a full quantum protocol involving initialization of the resonator in its quantum ground state of motion and subsequent generation and read-out of correlated photon-phonon pairs. The observed violation of a Cauchy-Schwarz inequality is clear evidence for the non-classical nature of the mechanical state generated. Our results demonstrate the availability of on-chip solid-state mechanical resonators as light-matter quantum interfaces. The performance we achieved will enable studies of macroscopic quantum phenomena8as well as applications in quantum communication9, as quantum memories10and as quantum transducers11,12.