The human settlement of the Pacific Islands represents one of the most recent major migration events of mankind. Polynesians originated in Asia according to linguistic evidence or in Melanesia according to archaeological evidence. To shed light on the genetic origins of Polynesians, we investigated over 400 Polynesians from 8 island groups, in comparison with over 900 individuals from potential parental populations of Melanesia, Southeast and East Asia, and Australia, by means of Y chromosome (NRY) and mitochondrial DNA (mtDNA) markers. Overall, we classified 94.1% of Polynesian Y chromosomes and 99.8% of Polynesian mtDNAs as of either Melanesian (NRY-DNA: 65.8%, mtDNA: 6%) or Asian (NRY-DNA: 28.3%, mtDNA: 93.8%) origin, suggesting a dual genetic origin of Polynesians in agreement with the "Slow Boat" hypothesis. Our data suggest a pronounced admixture bias in Polynesians toward more Melanesian men than women, perhaps as a result of matrilocal residence in the ancestral Polynesian society. Although dating methods are consistent with somewhat similar entries of NRY/mtDNA haplogroups into Polynesia, haplotype sharing suggests an earlier appearance of Melanesian haplogroups than those from Asia. Surprisingly, we identified gradients in the frequency distribution of some NRY/mtDNA haplogroups across Polynesia and a gradual west-to-east decrease of overall NRY/mtDNA diversity, not only providing evidence for a west-to-east direction of Polynesian settlements but also suggesting that Pacific voyaging was regular rather than haphazard. We also demonstrate that Fiji played a pivotal role in the history of Polynesia: humans probably first migrated to Fiji, and subsequent settlement of Polynesia probably came from Fiji.