Cueva de los Aviones (southeast Spain) is a site of the Neandertal-associated Middle Paleolithic of Europe. It has yielded ochred and perforated marine shells, red and yellow colorants, and shell containers that feature residues of complex pigmentatious mixtures. Similar finds from the Middle Stone Age of South Africa have been widely accepted as archaeological proxies for symbolic behavior. U-series dating of the flowstone capping the Cueva de los Aviones deposit shows that the symbolic finds made therein are 115,000 to 120,000 years old and predate the earliest known comparable evidence associated with modern humans by 20,000 to 40,000 years. Given our findings, it is possible that the roots of symbolic material culture may be found among the common ancestor of Neandertals and modern humans, more than half-a-million years ago.