Whether Neanderthals were capable of behaviours commonly held to be the exclusive preserve of modern humans — such as abstract thought, language, forward planning, art, reverence of the dead, complex technology, etc. — has remained a fundamental question in human evolutionary studies since their discovery more than a hundred years ago. A lack of quantitative data on Neanderthal symbolism and complex behaviour is a key obstacle to the resolution of this question, with temporal analyses usually confined to single regions or short time periods. Here we present an approach to the issue of symbolism and complex behaviours among Neanderthals that examines the frequency of key proxies for symbolic and complex behaviours through time, including burials, modified raw materials, use of pigments, use of composite technology and body modification. Our analysis demonstrates that the number and diversity of complex Neanderthal behaviours increases between 160,000 and 40,000 years ago. Whether this pattern derives from preservation factors, the evolution of cognitive and behavioural complexity, cumulative learning, or population size is discussed. We take the view that it is not the apparent sophistication of a single specific item, nor the presence or absence of particular types in the archaeological record that is important. Instead, we believe that it is the overall abundance of artefacts and features indicative of complex behaviours within the Neanderthal archaeological record as a whole that should provide the mark of Neanderthal capabilities and cultural evolutionary potential.