Sulawesi is the largest and oldest island within Wallacea, a vast zone of oceanic islands separating continental Asia from the Pleistocene landmass of Australia and Papua (Sahul). By one million years ago an unknown hominin lineage had colonized Flores immediately to the south, and by about 50 thousand years ago, modern humans ('Homo sapiens') had crossed to Sahul. On the basis of position, oceanic currents and biogeographical context, Sulawesi probably played a pivotal part in these dispersals. Uranium-series dating of speleothem deposits associated with rock art in the limestone karst region of Maros in southwest Sulawesi has revealed that humans were living on the island at least 40 thousand years ago. Here we report new excavations at Talepu in the Walanae Basin northeast of Maros, where in situ stone artefacts associated with fossil remains of megafauna ('Bubalus' sp., 'Stegodon' and 'Celebochoerus') have been recovered from stratified deposits that accumulated from before 200 thousand years ago until about 100 thousand years ago. Our findings suggest that Sulawesi, like Flores, was host to a long-established population of archaic hominins, the ancestral origins and taxonomic status of which remain elusive.