Cavity quantum electrodynamics (QED) studies the interaction between a quantum emitter and a single radiation-field mode. When an atom is strongly coupled to a cavity mode1, 2, it is possible to realize important quantum information processing tasks, such as controlled coherent coupling and entanglement of distinguishable quantum systems. Realizing these tasks in the solid state is clearly desirable, and coupling semiconductor self-assembled quantum dots to monolithic optical cavities is a promising route to this end. However, validating the efficacy of quantum dots in quantum information applications requires confirmation of the quantum nature of the quantum-dot–cavity system in the strong-coupling regime. Here we find such confirmation by observing quantum correlations in photoluminescence from a photonic crystal nanocavity3, 4, 5 interacting with one, and only one, quantum dot located precisely at the cavity electric field maximum. When off-resonance, photon emission from the cavity mode and quantum-dot excitons is anticorrelated at the level of single quanta, proving that the mode is driven solely by the quantum dot despite an energy mismatch between cavity and excitons. When tuned to resonance, the exciton and cavity enter the strong-coupling regime of cavity QED and the quantum-dot exciton lifetime reduces by a factor of 145. The generated photon stream becomes antibunched, proving that the strongly coupled exciton/photon system is in the quantum regime. Our observations unequivocally show that quantum information tasks are achievable in solid-state cavity QED.