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 atoms(1,2), atomic ensembles(3,4) or solids(5), 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 physics(6) and realizations of quantum networks(7). Here we report non-classical correlations between single photons and phonons-the quanta of mechanical motionfrom 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 phenomena(8) as well as applications in quantum communication(9), as quantum memories(10) and as quantum transducers(11,12).