African and Western Asian contemporaries of Neanderthals, generally considered to be the earliest Homo sapiens, are not particularly ‘modern’ looking in their cranial anatomy. Here we test whether the dental morphological signal agrees with this assessment. We used a Bayesian statistical approach to classifying individuals into ‘modern’ and ‘non-modern’ groups based on dental non-metric traits. The classification was based on dental trait frequencies for two ‘known’ samples of 109 Upper Paleolithic H. sapiens and 129 Neanderthal individuals. A cross-validation test of these individuals correctly classified them 95% of the time. Our early H. sapiens sample included 41 individuals from Southern Africa, Northern Africa and Western Asia. We treated our early H. sapiens individuals as ‘unknown’ and calculated the probability that each belonged to either the Upper Paleolithic or Neanderthal sample. We hypothesized that if the earliest H. sapiens were already dentally modern, then they would be assigned to the Upper Paleolithic H. sapiens group. We also hypothesized that if there had been significant admixture in Western Asia during the initial dispersal out of Africa, these samples would have the largest proportion of individuals classified as Neanderthal. Our results indicated that the latter was not the case. The smallest proportion of misclassified individuals came from Western Asia (7%) and the highest proportion of misclassified individuals came from Northern Africa (38%). In most cases it appears to be the predominance of primitive features, rather than derived Neanderthal traits that drove the classification. We conclude (1) by the time the earliest H. sapiens dispersed from Africa they had already attained a more-or-less modern dental pattern; (2) in the past, as is the case today, Late Pleistocene Africans were not a homogeneous group, some retained primitive dental traits in higher proportions than others. Furthermore, we acknowledge that while our method is an excellent tool for discriminating between Upper Paleolithic H. sapiens and Neanderthals, it may not be appropriate for testing Neanderthal – H. sapiens admixture because all traits (primitive and derived) are weighed equally. Moreover, to best assess admixture it is likely necessary to incorporate a model for how the traits track population history and/or gene flow.