We have used Y-chromosomal polymorphisms to trace paternal lineages in Polynesians by use of samples previously typed for mtDNA variants. A genealogical approach utilizing hierarchical analysis of eight rare-event biallelic polymorphisms, seven microsatellite loci, and internal structural analysis of the hypervariable minisatellite, MSY1, has been used to define three major paternal-lineage clusters in Polynesians. Two of these clusters, both defined by novel MSY1 modular structures and representing 55% of the Polynesians studied, are also found in coastal Papua New Guinea. Reduced Polynesian diversity, relative to that in Melanesians, is illustrated by the presence of several examples of identical MSY1 codes and microsatellite haplotypes within these lineage clusters in Polynesians. The complete lack of Y chromosomes having the M4 base substitution in Polynesians, despite their prevalence (64%) in Melanesians, may also be a result of the multiple bottleneck events during the colonization of this region of the world. The origin of the M4 mutation has been dated by use of two independent methods based on microsatellite-haplotype and minisatellite-code diversity. Because of the wide confidence limits on the mutation rates of these loci, the M4 mutation cannot be conclusively dated relative to the colonization of Polynesia, 3,000 years ago. The other major lineage cluster found in Polynesians, defined by a base substitution at the 92R7 locus, represents 27% of the Polynesians studied and, most probably, originates in Europe. This is the first Y-chromosomal evidence of major European admixture with indigenous Polynesian populations and contrasts sharply with the picture given by mtDNA evidence.