The interpretation of genetic evidence regarding modern human origins depends, among other things, on assessments of the structure and the variation of ancient populations. Because we lack genetic data from the time when the first anatomically modern humans appeared, between 200,000 and 60,000 years ago, instead we exploit the phenotype of neurocranial geometry to compare the variation in early modern human fossils with that in other groups of fossil Homo and recent modern humans. Variation is assessed as the mean-squared Procrustes distance from the group average shape in a representation based on several hundred neurocranial landmarks and semilandmarks. We find that the early modern group has more shape variation than any other group in our sample, which covers 1.8 million years, and that they are morphologically similar to recent modern humans of diverse geographically dispersed populations but not to archaic groups. Of the currently competing models of modern human origins, some are inconsistent with these findings. Rather than a single out-of-Africa dispersal scenario, we suggest that early modern humans were already divided into different populations in Pleistocene Africa, after which there followed a complex migration pattern. Our conclusions bear implications for the inference of ancient human demography from genetic models and emphasize the importance of focusing research on those early modern humans, in particular, in Africa.