quality:corruption
Paleolithic

Island Southeast Asia was settled by modern humans in the Paleolithic following coastal migration routes, presumably starting before 70,000 BP from Africa, long before the development of Austronesian cultures. These populations are typified by having dark skin, curly hair, and short statures, leading Europeans to believe, in the 19th century, that they were related to African Pygmies. However, despite these physical similarities, genetic studies have shown that they are more closely related to other Eurasian populations than to Africans.

The lowered sea levels of the Pleistocene made some of the modern-day islands of Sundaland accessible via land bridges. However, the spread of humans across the Wallace line and into Sahul necessitated crossing bodies of water. Remains of stone tools and marine shells in Liang Sarru, Salibabu Island, North Sulawesi, dated to 32,000–35,000 years ago, is possible evidence for the longest sea voyage by Paleolithic humans ever recorded. The island was previously uninhabited by humans or hominins and can only be reached from either Mindanao or the Sangihe Islands by crossing an expanse of water at least 100 km (62 mi) wide, even during the low sea levels of the Pleistocene. Other evidence of early maritime transport are the appearance of obsidian tools with the same source on neighboring islands. These include the Philippine obsidian network (Mindoro and Palawan, ca.33,000-28,000 BP), and the Wallacea obsidian network (Timor, Atauro, Kisar, Alor, ca.22,000 BP). However, the method of crossing remains unknown and could have ranged from simple rafts to dugout canoes by the terminal Pleistocene.

These early settlers are generally historically referred to as " Australo-Melanesians ", though the terminology is problematic, as they are genetically diverse, and most groups within Austronesia have significant Austronesian admixture and culture. The unmixed descendants of these groups today include the interior Papuans and Indigenous Australians.

In modern literature, descendants of these groups, located in Island Southeast Asia west of Halmahera, are usually collectively referred to as " Negritos ", while descendants of these groups east of Halmahera (excluding Indigenous Australians) are referred to as " Papuans ". They can also be divided into two broad groups based on Denisovan admixture. Philippine Negritos, Papuans, Melanesians, and Indigenous Australians display Denisovan admixture, while Malaysian and western Indonesian Negritos (Orang Asli) and Andamanese islanders do not.

Mahdi (2017) also uses the term "Qata" (from Proto-Malayo-Polynesian *qata) to distinguish the indigenous populations of Southeast Asia, versus "Tau" (from Proto-Austronesian *Cau) for the later settlers from Taiwan and mainland China. Both are based on proto-forms for the word "person" in Malayo-Polynesian languages that referred to darker-skinned and lighter-skinned groups, respectively. Jinam et al. (2017) also proposed the term "First Sundaland People" in place of "Negrito", as a more accurate name for the original population of Southeast Asia.

These populations are genetically distinct from later Austronesians, but through fairly extensive population admixture, most modern Austronesians have varying levels of ancestry from these groups. The same is true for some populations historically considered "non-Austronesians", due to physical differences—like Philippine Negritos, Orang Asli, and Austronesian-speaking Melanesians, all of whom have Austronesian admixture. In Polynesians in Remote Oceania, for example, the admixture is around 20 to 30% Papuan and 70 to 80% Austronesian. The Melanesians in Near Oceania are roughly around 20% Austronesian and 80% Papuan, while in the natives of the Lesser Sunda Islands, the admixture is around 50% Austronesian and 50% Papuan. Similarly, in the Philippines, the groups traditionally considered to be "Negrito" vary between 30 and 50% Austronesian.

The high degree of assimilation among Austronesian, Negrito, and Papuan groups indicates that the Austronesian expansion was largely peaceful. Rather than violent displacement, the settlers and the indigenous groups absorbed each other. It is believed that in some cases, like in the Toalean culture of Sulawesi (c. 8,000–1,500 BP), it is even more accurate to say that the densely populated indigenous hunter-gatherer groups absorbed the incoming Austronesian farmers, rather than the other way around. Mahdi (2016) further asserts that Proto-Malayo-Polynesian *tau-mata ("person") is derived from a composite protoform *Cau ma-qata, combining "Tau" and "Qata" and indicative of the mixing of the two ancestral population types in these regions.