Quantum-mechanically correlated (entangled) states of many particles are of interest for quantum information, quantum computing and quantum metrology. Only recently has it become possible to generate many-atom entangled states, and to use them to outperform measurements done with collections of independent atoms. Here we generate entanglement in a large atomic ensemble via an interaction with a very weak laser pulse; remarkably, the detection of a single photon prepares several thousand atoms in an entangled state. We reconstruct a negative-valued quasiprobability function, a hallmark of non-classicality, and verify that at least 2,900 out of 3,100 atoms must be entangled with one another. Furthermore we discuss prospects for generating more and more complex entangled states that can be used to improve quantum measurements.