Human presence in Southeast Asia dates back to at least 40,000 years ago, when the current islands formed a continental shelf called Sundaland. In the Philippine Islands, Peninsular Malaysia, and Andaman Islands, there exist indigenous groups collectively called Negritos whose ancestry can be traced to the "First Sundaland People." To understand the relationship between these Negrito groups and their demographic histories, we generated genome-wide single nucleotide polymorphism data in the Philippine Negritos and compared them with existing data from other populations. Phylogenetic tree analyses show that Negritos are basal to other East and Southeast Asians, and that they diverged from West Eurasians at least 38,000 years ago. We also found relatively high traces of Denisovan admixture in the Philippine Negritos, but not in the Malaysian and Andamanese groups, suggesting independent introgression and/or parallel losses involving Denisovan introgressed regions. Shared genetic loci between all three Negrito groups could be related to skin pigmentation, height, facial morphology and malarial resistance. These results show the unique status of Negrito groups as descended from the First Sundaland People.