Southeast Asia (SEA) is enriched with a complex history of peopling. Malaysia, which is located at the crossroads of SEA, has been recognized as one of the hubs for early human migration. To unravel the genomic complexity of the native inhabitants of Malaysia, we sequenced 12 samples from 3 indigenous populations from Peninsular Malaysia and 4 native populations from North Borneo to a high coverage of 28-37×. We showed that the Negritos from Peninsular Malaysia shared a common ancestor with the East Asians, but exhibited some level of gene flow from South Asia, while the North Borneo populations exhibited closer genetic affinity towards East Asians than the Malays. The analysis of time of divergence suggested that ancestors of Negrito were the earliest settlers in the Malay Peninsula, whom first separated from the Papuans ~ 50-33 thousand years ago (kya), followed by East Asian (~ 40-15 kya), while the divergence time frame between North Borneo and East Asia populations predates the Austronesian expansion period implies a possible pre-Neolithic colonization. Substantial Neanderthal ancestry was confirmed in our genomes, as was observed in other East Asians. However, no significant difference was observed, in terms of the proportion of Denisovan gene flow into these native inhabitants from Malaysia. Judging from the similar amount of introgression in the Southeast Asians and East Asians, our findings suggest that the Denisovan gene flow may have occurred before the divergence of these populations and that the shared similarities are likely an ancestral component.