Over 60 years ago, stone tools and remains of megafauna were discovered on the Southeast Asian islands of Flores, Sulawesi and Luzon, and a Middle Pleistocene colonization by Homo erectus was initially proposed to have occurred on these islands. However, until the discovery of Homo floresiensis in 2003, claims of the presence of archaic hominins on Wallacean islands were hypothetical owing to the absence of in situ fossils and/or stone artefacts that were excavated from well-documented stratigraphic contexts, or because secure numerical dating methods of these sites were lacking. As a consequence, these claims were generally treated with scepticism. Here we describe the results of recent excavations at Kalinga in the Cagayan Valley of northern Luzon in the Philippines that have yielded 57 stone tools associated with an almost-complete disarticulated skeleton of Rhinoceros philippinensis, which shows clear signs of butchery, together with other fossil fauna remains attributed to stegodon, Philippine brown deer, freshwater turtle and monitor lizard. All finds originate from a clay-rich bone bed that was dated to between 777 and 631 thousand years ago using electron-spin resonance methods that were applied to tooth enamel and fluvial quartz. This evidence pushes back the proven period of colonization of the Philippines by hundreds of thousands of years, and furthermore suggests that early overseas dispersal in Island South East Asia by premodern hominins took place several times during the Early and Middle Pleistocene stages. The Philippines therefore may have had a central role in southward movements into Wallacea, not only of Pleistocene megafauna, but also of archaic hominins.