The variability observed in the growing Middle Pleistocene hominin fossil record of Europe continues to trigger much debate on taxonomic issues and the biological processes that gave rise to Neanderthals. Here we present a metric and morphological comparative study of the dental samples recovered from the sites of Arago (southeast France) and Sima de los Huesos (SH) in the Sierra de Atapuerca (northern Spain). These sites are key to providing answers to these questions since they have yielded the largest hominin samples so far recovered for this time period. Despite the geographical proximity of the two sites and the contemporaneity of their hominin assemblages, we have observed remarkable metric and morphological differences between the teeth at Arago and SH. Whereas the SH teeth present an almost morphological identity with European Neanderthals, the Arago teeth exhibit a combination of plesiomorphic as well as some Neanderthal-derived features. In addition, the Arago crown dimensions are remarkably larger than those from SH, the differences being statistically significant for most variables. We hypothesize that during the Middle Pleistocene the European continent was settled at different points in time by hominin groups coming from Southwest Asia, probably from a common mother population evolving in this latter region. These first settlers can be identified by their more plesiomorphic morphology, whereas the most recent settlers are closer in appearance to Neanderthals. In addition, genetic processes such as isolation, genetic drift, directional adaptation or hybridization would have given rise to the puzzle we observe in the current fossil record.