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 region(3). Claims that AMH arrived in ISEA before 60 ka (ref. 4) have been supported only by equivocal(5) or non-skeletal evidence(6). AMH evidence from this period is rare and lacks robust chronologies owing to a lack of direct dating applications(7), poor preservation and/or excavation strategies(8) and questionable taxonomic identifications(9). Lida Ajer is a Sumatran Pleistocene cave with a rich rainforest fauna associated with fossil human teeth(7,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 estimations(7), palaeoclimate and sea-level reconstructions, and genetic evidence for a pre-60 ka arrival of AMH into ISEA(2). 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.