Human paternal population history was studied in 9 populations [three Native American, three Asian, two Caucasian and one African-derived sample(s)] using sequence and short tandem repeat haplotype diversity within the non-pseudoautosegmal region of the Y chromosome. Complete coding and additional flanking sequences (949 base pairs) of the RPS4Y locus were determined in 59 individuals from three of the populations, revealing a nucleotide diversity of 0.0147%, consistent with previous estimates from Y chromosome resequencing studies. One RPS4Y sequence variant, 711C>T, was polymorphic in Asian and Native American populations, but not in African and Caucasian population samples. The RPS4Y 711C>T variant, a second unique sequence variant at DYS287 and nine Y chromosome short tandem repeat (YSTR) loci were used to analyze the evolution of Y chromosome lineages. Three unambiguous lineages were defined in Asian, Native American and Jamaican populations using sequence variants at RPS4Y and DYS287. These lineages were independently supported by the haplotypes defined solely by YSTR alleles, demonstrating the haplotypes constructed from YSTRs can evaluate population diversity, admixture and phylogeny.