In the nonrecombining region of the Y-chromosome, there are single-nucleotide polymorphisms (Y-SNPs) that establish haplogroups with particular geographical origins (European, African, Native American, etc.). The complex process of admixture that gave rise to the majority of the current Mexican population (~93%), known as Mestizos, can be examined with Y-SNPs to establish their paternal ancestry and population structure. We analyzed 18 Y-SNPs in 659 individuals from 10 Mexican-Mestizo populations from different regions of the country. In the total population sample, paternal ancestry was predominately European (64.9%), followed by Native American (30.8%) and African (4.2%). However, the European ancestry was prevalent in the north and west (66.7-95%) and, conversely, Native American ancestry increased in the center and southeast (37-50%), whereas the African ancestry was low and relatively homogeneous (0-8.8%). Although this paternal landscape concurs with previous studies based on genome-wide SNPs and autosomal short tandem repeats (STRs), this pattern contrasts with the maternal ancestry, mainly of Native American origin, based on maternal lineages haplogroups. In agreement with historical records, these results confirm a strong gender-biased admixture history between European males and Native American females that gave rise to Mexican-Mestizos. Finally, pairwise comparisons and analysis of molecular variance tests demonstrated significant population structure (F(ST)=4.68%; P<0.00005), delimiting clusters that were geographically defined as the following: north-west, center-south and southeast.