Modern humans reached Southeast Asia and Oceania in one of the first dispersals out of Africa. The resulting temporal overlap of modern and archaic humans-and the apparent morphological continuity between them-has led to claims of gene flow between Homo sapiens and H. erectus. Much more recently, an agricultural technology from mainland Asia spread into the region, possibly in association with Austronesian languages. Using detailed genealogical study of Y chromosome variation, we show that the majority of current Austronesian speakers trace their paternal heritage to Pleistocene settlers in the region, as opposed to more-recent agricultural immigrants. A fraction of the paternal heritage, however, appears to be associated with more-recent immigrants from northern populations. We also show that the northern Neolithic component is very unevenly dispersed through the region, with a higher contribution in Southeast Asia and a nearly complete absence in Melanesia. Contrary to claims of gene flow (under regional continuity) between H. erectus and H. sapiens, we found no ancestral Y chromosome lineages in a set of 1,209 samples. The finding excludes the possibility that early hominids contributed significantly to the paternal heritage of the region.