Les plus anciennes preuves de l'existence de la navigation dans l'espace Asie-Pacifique datent de 800 000 ans environ. A cette époque, la configuration d'une partie de l'Asie du Sud-Est et du monde Océanien est différente. Le niveau de la mer étant beaucoup plus bas, les principales îles indonésiennes actuelles (Java, Sumatra, Bornéo) sont rattachées au continent sud-est asiatique tandis que l'Australie et la Nouvelle-Guinée appartiennent au même sous-continent nommé Sahul. Il existe cependant un zone intermédiaire encastrée entre Java et Bornéo d'une part et la Nouvelle-Guinée d'autre part, qui reste parsemée d'îles.

Or, des récentes découvertes archéologiques ont révélé que Homo erectus a pu atteindre ces îles, il y a 800 000 à 900 000 ans. L'accès à l'île de Florès notamment, exigea l'utilisation d'embarcations sans doute rudimentaires. On peut également penser que vers 30 000 ans avant J.C, la maîtrise de la navigation par l'homme moderne a favorisé la colonisation des îles de Mélanésie orientale, telles que la Nouvelle-Guinée, la Nouvelle-Bretagne, la Nouvelle-Irlande jusqu'à l'île Buka (archipel des Salomon).