The origin of Neanderthal and modern human lineages is a matter of intense debate. DNA analyses have generally indicated that both lineages diverged during the middle period of the Middle Pleistocene, an inferred time that has strongly influenced interpretations of the hominin fossil record. This divergence time, however, is not compatible with the anatomical and genetic Neanderthal affinities observed in Middle Pleistocene hominins from Sima de los Huesos (Spain), which are dated to 430 thousand years (ka) ago. Drawing on quantitative analyses of dental evolutionary rates and Bayesian analyses of hominin phylogenetic relationships, I show that any divergence time between Neanderthals and modern humans younger than 800 ka ago would have entailed unexpectedly rapid dental evolution in early Neanderthals from Sima de los Huesos. These results support a pre-800 ka last common ancestor for Neanderthals and modern humans unless hitherto unexplained mechanisms sped up dental evolution in early Neanderthals.