Fossil remains from Java show that early humans (Homo erectus) first entered the region more than one million years ago. Evidence suggests they were replaced by the incoming ancestors of modern humans less than 150,000 years ago. Traces of H. erectus have not yet been found in Malysia where the record of humanity, according to radiocarbon dating methods, begins about 40,000 years ago. These early humans had to cope with many environmental changes. When sea levels were low during the Pleistocene, they could have used the land bridges connecting mainland Asia to Sumatra, Java and Borneo, or they may have crossed the sea using rafts.
The initial people of Malaysia is both a story of great fastination and a source of heated debate. The first modern human occupants were quite closely related to the first Australo-Melanesian colonists of western Melanesia and Australia. Excavations in the Niah Caves of Sarawak have produced numerous remains of these people, dating from possibly 40,000 years ago and onwards, while Peninsular Malaysian rock shelters with evidence of Hoabinhian occupation, such as Gua Cha, also have skeletal remains of a related population who first penetrated the interior rainforests about 12,000 years ago.
Opinions differ as to whether present-day Malaysians descend entirely from Pleistocene founder populations or from subsequent migrations. It is the author's view that 3,000 - 4,000 years ago Austronesian-speaking people from Taiwan dispersed through the islands of Southeast Asia fundamentally altering the human shape of Malaysia. All the indigenous Borneans today are Austronesians, who perhaps first colonised Borneo 3,500 years ago, as evidenced by finds in Sabah at the Madai Caves and at Bukit Tengkorak, and in the Niah and Mulu Caves of Sarawak.
Peninsular Malaysia is quite different, and much more diverse ethnically. Among the Orang Asli, the Negritos probably descend from the tool-makers of the Hoabinhian cultural period, whereas the ancestry of the Senoi agriculturalists may derive from people practising a mixed Hoabinhian and Neolithic culture, the latter involving migrations from Thailand 4,000 years ago. Both groups speak Austroasiatic languages unrelated to Austronesian. The Malays are Austronesians, but it is not sure when they first settled in the Malay Peninsula. Archaeology suggests that the Peninsula was still mainly occupied by Semang hunters and Senoi agriculturalists as recently as 2,000 years ago. The first major spread of the Malay language might have occurred during the period of Srivijaya after 670 CE. At a similar date, Malay perhaps first spread to Borneo as a trade language.
.....page 11 The Encyclopedia of Malaysia - Early History.