The non-recombining nature of the Y chromosome and the well-established phylogeny of Y-specific Single Nucleotide Polymorphisms (Y-SNPs) make them useful for defining haplogroups with high geographical specificity; therefore, they are more apt than the Y-STRs to detect population stratification in admixed populations from diverse continental origins. Different Y-SNP typing strategies have been described to address issues of population history and movements within geographic territories of interest. In this study, we investigated a set of 41 Y-SNPs in 1217 unrelated males from the five Brazilian geopolitical regions, aiming to disclose the genetic structure of male lineages in the country. A population comparison based on pairwise FST genetic distances did not reveal statistically significant differences in haplogroup frequency distributions among populations from the different regions. The genetic differences observed among regions were, however, consistent with the colonization history of the country. The sample from the Northern region presented the highest Native American ancestry (8.4%), whereas the more pronounced African contribution could be observed in the Northeastern population (15.1%). The Central-Western and Southern samples showed the higher European contributions (95.7% and 93.6%, respectively). The Southeastern region presented significant European (86.1%) and African (12.0%) contributions. The subtyping of the most frequent European lineage in Brazil (R1b1a-M269) allowed differences in the genetic European background of the five Brazilian regions to be investigated for the first time.