Mestizos currently represent most of the Mexican population (>90%); they are defined as individuals born in the country having a Spanish-derived last name, with family antecedents of Mexican ancestors back at least to the third generation. Mestizos are result of 500 years of admixture mainly among Spaniards, Amerindians, and African slaves. Consequently, a complex genetic pattern has been generated throughout the country that has been scarcely studied from the paternal point of view. This fact is important, taking into account that gene flow toward the New World comprised largely males. We analyzed the population structure and paternal admixture of present-day Mexican-Mestizo populations based on Y-STRs. We genotyped at least 12 Y-STRs in DNA samples of 986 males from five states: Aguascalientes (n = 293); Jalisco (n = 185); Guanajuato (n = 168); Chiapas (n = 170); and Yucatán (n = 170). AmpFlSTR Y-filer and Powerplex-Y(R) kits were used. Inclusion of North and Central Y-STR databases in the analyses allowed obtaining a Y-STR variability landscape from Mexico. Results confirmed the population differentiation gradient previously noted in Mestizos with SNPs and autosomal STRs throughout the Mexican territory: European ancestry increments to the Northwest and, correspondingly, Amerindian ancestry increments to the Center and Southeast. In addition, SAMOVA test and Autocorrelation Index for DNA Analysis autocorrelogram plot suggested preferential gene flow of males with neighboring populations in agreement with the isolation-by-distance model. Results are important for disease-risk studies (principally male-related) and for human identification purposes, because Y-STR databases are not available on the majority of Mexican-Mestizo populations.