The archaeological record of Africa provides the earliest evidence for the emergence of the complex symbolic and technological behaviours that characterize Homo sapiens1���7. The coastal setting of many archaeological sites of the Late Pleistocene epoch, and the abundant shellfish remains recovered from them, has led to a dominant narrative in which modern human origins in southern Africa are intrinsically tied to the coast and marine resources8���12, and behavioural innovations in the interior lag behind. However, stratified Late Pleistocene sites with good preservation and robust chronologies are rare in the interior of southern Africa, and the coastal hypothesis therefore remains untested. Here we show that early human innovations that are similar to those dated to around 105��thousand years ago (ka) in coastal southern Africa existed at around the same time among humans who lived over 600��km inland. We report evidence for the intentional collection of non-utilitarian objects (calcite crystals) and ostrich eggshell from excavations of a stratified rockshelter deposit in the southern Kalahari Basin, which we date by optically stimulated luminescence to around 105��ka. Uranium���thorium dating of relict tufa deposits indicates sporadic periods of substantial volumes of fresh, flowing water; the oldest of these episodes is dated to between 110 and 100��ka and is coeval with the archaeological deposit. Our results suggest that behavioural innovations among humans in the interior of southern Africa did not lag behind those of populations near the coast, and that these innovations may have developed within a wet savannah environment. Models that tie the emergence of behavioural innovations to the exploitation of coastal resources by our species may therefore require revision.