Genetic evidence for anatomically modern humans (AMH) out of Africa before 75 thousand years ago (ka)1 and in island southeast Asia (ISEA) before 60 ka (93–61 ka)2 predates accepted archaeological records of occupation in the region3. Claims that AMH arrived in ISEA before 60 ka (ref. 4) have been supported only by equivocal5 or non-skeletal evidence6. AMH evidence from this period is rare and lacks robust chronologies owing to a lack of direct dating applications7, poor preservation and/or excavation strategies8 and questionable taxonomic identifications9. Lida Ajer is a Sumatran Pleistocene cave with a rich rainforest fauna associated with fossil human teeth7, 10. The importance of the site is unclear owing to unsupported taxonomic identification of these fossils and uncertainties regarding the age of the deposit, therefore it is rarely considered in models of human dispersal. Here we reinvestigate Lida Ajer to identify the teeth confidently and establish a robust chronology using an integrated dating approach. Using enamel–dentine junction morphology, enamel thickness and comparative morphology, we show that the teeth are unequivocally AMH. Luminescence and uranium-series techniques applied to bone-bearing sediments and speleothems, and coupled uranium-series and electron spin resonance dating of mammalian teeth, place modern humans in Sumatra between 73 and 63 ka. This age is consistent with biostratigraphic estimations7, palaeoclimate and sea-level reconstructions, and genetic evidence for a pre-60 ka arrival of AMH into ISEA2. Lida Ajer represents, to our knowledge, the earliest evidence of rainforest occupation by AMH, and underscores the importance of reassessing the timing and environmental context of the dispersal of modern humans out of Africa.