The genetic ancestry of Polynesians can be traced to both Asia and Melanesia, which presumably reflects admixture occurring between incoming Austronesians and resident non-Austronesians in Melanesia before the subsequent occupation of the greater Pacific; however, the genetic impact of the Austronesian expansion to Melanesia remains largely unknown. We therefore studied the diversity of nonrecombining Y chromosomal (NRY) and mitochondrial (mt) DNA in the Admiralty Islands, located north of mainland Papua New Guinea, and updated our previous data from Asia, Melanesia, and Polynesia with new NRY markers. The Admiralties are occupied today solely by Austronesian-speaking groups, but their human settlement history goes back 20,000 years prior to the arrival of Austronesians about 3,400 years ago. On the Admiralties, we found substantial mtDNA and NRY variation of both Austronesian and non-Austronesian origins, with higher frequencies of Asian mtDNA and Melanesian NRY haplogroups, similar to previous findings in Polynesia and perhaps as a consequence of Austronesian matrilocality. Thus, the Austronesian language replacement on the Admiralties (and elsewhere in Island Melanesia and coastal New Guinea) was accompanied by an incomplete genetic replacement that is more associated with mtDNA than with NRY diversity. These results provide further support for the "Slow Boat" model of Polynesian origins, according to which Polynesian ancestors originated from East Asia but genetically mixed with Melanesians before colonizing the Pacific. We also observed that non-Austronesian groups of coastal New Guinea and Island Melanesia had significantly higher frequencies of Asian mtDNA haplogroups than of Asian NRY haplogroups, suggesting sex-biased admixture perhaps as a consequence of non-Austronesian patrilocality. We additionally found that the predominant NRY haplogroup of Asian origin in the Admiralties (O-M110) likely originated in Taiwan, thus providing the first direct Y chromosome evidence for a Taiwanese origin of the ...