New evidence from Lene Hara Cave, East Timor, demonstrates that it was first occupied by modern humans by 42,454±450 cal BP at approximately the same time as nearby Jerimalai shelter. Together these sites constitute the earliest evidence for modern human colonisation of Island Southeast Asia east of the Sunda Shelf. Here we report on the dating and stratigraphy from the 2000 and 2002 test excavations at Lene Hara, as well as new dates obtained by sampling breccia deposits in 2009. The post-2000 excavations and sampling demonstrate that different areas of the cave preserve different sedimentary sequences and necessitate a revision of our earlier interpretations of the occupation history of the cave. At Lene Hara, and other caves with complex depositional histories in tropical regions, the occupation sequence will only be revealed through integrating information from extensive areal sampling. When calibrated, the early dates from East Timor now align closer to the oldest evidence for occupation in northern Australia, with substantial implications for current theories on the colonisation of this region by modern humans. The Nusa Tenggara (Lesser Sunda) island chain emerges as a likely passage for modern human entry into Greater Australia. In view of the short water crossings required to reach Flores from Timor, the apparent absence of modern humans on Flores prior to the Holocene appears highly anomalous.