Using mitochondrial lineage analysis of 1,178 individuals from Polynesia, the western Pacific, and Taiwan, we show that the major prehistoric settlement of Polynesia was from the west and involved two or possibly three genetically distinct populations. The predominant lineage group, accounting for 94% of Polynesian mtDNA, shares a 9-bp COII/tRNA (Lys) intergenic deletion and characteristic control region transition variants, compared to the Cambridge reference sequence. In Polynesia, the diversity of this group is extremely restricted, while related lineages in Indonesia, the Philippines, and Taiwan are increasingly diverse. This suggests a relatively recent major eastward expansion into Polynesia, perhaps originating from Taiwan, in agreement with archeological and linguistic evidence, but which experienced one or more severe population bottlenecks. The second mitochondrial lineage group, accounting for 3.5% of Polynesian mtDNA haplotypes, does not have the 9-bp deletion and its characterized by an AC transversional variant at nt position 16265. Specific oligonucleotides for this variant were used to select individuals from the population sample who, with other sequences, show that the Polynesian lineages were part of a diverse group in Vanuatu and Papua New Guinea. The very low overall diversity of both lineage groups in Polynesia suggests there was severe population restriction during the colonization of remote Oceania. A third group, represented by only four individuals (0.6%) in Polynesia but also present in the Philippines, shares variants at nt positions 16172 and 16304. Two Polynesians had unrelated haplotypes matching published sequences from native South Americans, which may be the first genetic evidence of prehistoric human contact between Polynesia and South America.