This paper reviews the histories approach to quantum mechanics. This discussion is then applied to theories of quantum gravity. It is argued that some of the quantum histories must approximate (in a suitable sense) to classical histories, if the correct classical regime is to be recovered. This observation has significance for the formulation of new theories (such as quantum gravity theories) as it puts a constraint on the kinematics, if the quantum/classical correspondence principle is to be preserved. Consequences for quantum gravity, particularly for Lorentz symmetry and the idea of "emergent geometry", are discussed.