In a large variety of genetic studies, probabilistic inferences are made based on information available in population databases. The accuracy of the estimates based on population samples are highly dependent on the number of chromosomes being analyzed as well as the correct representation of the reference population. For frequency calculations the size of a database is especially critical for haploid markers, and for countries with complex admixture histories it is important to assess possible substructure effects that can influence the coverage of the database. Aiming to establish a representative Brazilian population database for haplotypes based on 23 Y chromosome STRs, more than 2,500 Y chromosomes belonging to Brazilian, European and African populations were analyzed. No matter the differences in the colonization history of the five geopolitical regions that currently exist in Brazil, for the Y chromosome haplotypes of the 23 studied Y-STRs, a lack of genetic heterogeneity was found, together with a predominance of European male lineages in all regions of the country. Therefore, if we do not consider the diverse Native American or Afro-descendent isolates, which are spread through the country, a single Y chromosome haplotype frequency database will adequately represent the urban populations in Brazil. In comparison to the most commonly studied group of 17 Y-STRs, the 23 markers included in this work allowed a high discrimination capacity between haplotypes from non-related individuals within a population and also increased the capacity to discriminate between paternal relatives. Nevertheless, the expected haplotype mutation rate is still not enough to distinguish the Y chromosome profiles of paternally related individuals. Indeed, even for rapidly mutating Y-STRs, a very large number of markers will be necessary to differentiate male lineages from paternal relatives.