Western Eurasia yielded a rich Middle (MP) and Late Pleistocene (LP) fossil record documenting the evolution of the Neandertals that can be analyzed in light of recently acquired paleogenetical data, an abundance of archeological evidence, and a well-known environmental context. Their origin likely relates to an episode of recolonization of Western Eurasia by hominins of African origin carrying the Acheulean technology into Europe around 600 ka. An enhancement of both glacial and interglacial phases may have played a crucial role in this event, as well as in the subsequent evolutionary history of the Western Eurasian populations. In addition to climatic adaptations and an increase in encephalization, genetic drift seems to have played a major role in their evolution. To date, a clear speciation event is not documented, and the most likely scenario for the fixation of Neandertal characteristics seems to be an accretion of features along the second half of the MP. Although a separation time for the African and Eurasian populations is difficult to determine, it certainly predates OIS 11 as phenotypic Neandertal features are documented as far back as and possibly before this time. It is proposed to use the term "Homo rhodesiensis" to designate the large-brained hominins ancestral to H. sapiens in Africa and at the root of the Neandertals in Europe, and to use the term "Homo neanderthalensis" to designate all of the specimens carrying derived metrical or non-metrical features used in the definition of the LP Neandertals.