The information carrier of today's communications, a weak pulse of light, is an intrinsically quantum object. As a consequence, complete information about the pulse cannot be perfectly recorded in a classical memory, even in principle. In the field of quantum information, this has led to the long-standing challenge of how to achieve a high-fidelity transfer of an independently prepared quantum state of light onto an atomic quantum state. Here we propose and experimentally demonstrate a protocol for such a quantum memory based on atomic ensembles. Recording of an externally provided quantum state of light onto the atomic quantum memory is achieved with 70 per cent fidelity, significantly higher than the limit for classical recording. Quantum storage of light is achieved in three steps: first, interaction of the input pulse and an entangling field with spin-polarized caesium atoms; second, subsequent measurement of the transmitted light; and third, feedback onto the atoms using a radio-frequency magnetic pulse conditioned on the measurement result. The density of recorded states is 33 per cent higher than the best classical recording of light onto atoms, with a quantum memory lifetime of up to 4 milliseconds.