Anthropologists have long been fascinated by the isolated hunter-gatherer populations in Southeast Asia (SEA) collectively known as "Negritos." However, the origins and affinities of these groups remain unresolved. Negritos are characterized by their short stature, dark skin color, and wiry hair, and they inhabit the Philippines, Malay Peninsula, and the Andaman Islands. Among Philippine Negritos, the Batak are of particular interest in understanding population interactions in the region due to their location on Palawan Island, which likely formed a corridor by which human migrations entered the rest of the Philippine archipelago from Island SEA. Here, we extend current understanding of the distribution of genetic diversity in Negritos by presenting the first analysis of mitochondrial DNA and Y-chromosome diversity among the Batak. We show that the Batak are genetically distinct from Negritos of the Andaman Islands and Malay Peninsula and instead bear most resemblance to geographically proximate Philippine Negritos and to non-Negrito populations from the Philippines and Island SEA. An extensive degree of recent admixture between the Batak and their neighbors is indicated by the high frequency of recently coalescing haplogroups in the Batak that are found throughout Island SEA. The comparison of results from these two loci further lends support to the hypothesis that male-biased admixture has, in particular, been a prominent feature of the interactions between the Batak and surrounding non-Negrito populations.