Nano- and micromechanical solid-state quantum devices have become a focus of attention. Reliably generating nonclassical states of their motion is of interest both for addressing fundamental questions about macroscopic quantum phenomena and for developing quantum technologies in the domains of sensing and transduction. We used quantum optical control techniques to conditionally generate single-phonon Fock states of a nanomechanical resonator. We performed a Hanbury Brown and Twiss–type experiment that verified the nonclassical nature of the phonon state without requiring full state reconstruction. Our result establishes purely optical quantum control of a mechanical oscillator at the single-phonon level.