Approximately 700,000 years ago, Homo erectus in Africa was giving way to populations with larger brains accompanied by structural adjustments to the vault, cranial base, and face. Such early Middle Pleistocene hominins were not anatomically modern. Their skulls display strong supraorbital tori above projecting faces, flattened frontals, and less parietal expansion than is the case for Homo sapiens. Postcranial remains seem also to have archaic features. Subsequently, some groups evolved advanced skeletal morphology, and by ca. 200,000 years ago, individuals more similar to recent humans are present in the African record. These fossils are associated with Middle Stone Age lithic assemblages and, in some cases, Acheulean tools. Crania from Herto in Ethiopia carry defleshing cutmarks and superficial scoring that may be indicative of mortuary practices. Despite these signs of behavioral innovation, neither the Herto hominins, nor others from Late Pleistocene sites such as Klasies River in southern Africa and Skhūl/Qafzeh in Israel, can be matched in living populations. Skulls are quite robust, and it is only after ≈35,000 years ago that people with more gracile, fully modern morphology make their appearance. Not surprisingly, many questions concerning this evolutionary history have been raised. Attention has centered on systematics of the mid-Pleistocene hominins, their paleobiology, and the timing of dispersals that spread H. sapiens out of Africa and across the Old World. In this report, I discuss structural changes characterizing the skulls from different time periods, possible regional differences in morphology, and the bearing of this evidence on recognizing distinct species.