Y-STR haplotypes are widely studied in Europe and an extensive databasing effort has been conducted (http://www.ystr.org). The distribution of these haplotypes has been considered to present no evidence for substructure at central and southern European level. This picture contrasts with the one that results from Y haplogroups defined by binary markers. This paradox has been solved by admitting that the high STR mutation rate and corresponding recurrence has erased geographic structuration. This explanation prompted us to reanalyse Y-STR haplotypes distribution bearing in mind the commonly admitted model for the generation of diversity in these markers, namely the stepwise mutation model (SMM) and, thus, taking the molecular distance between haplotypes into consideration. Accordingly, we have studied the European distribution of the two most frequent haplotypes in the Iberian Peninsula and their one step neighbours using the European samples deposited in the Y STR database (http://www.ystr.org). For the first group we found a clear-cut decreasing W-E gradient, while for the second the highest frequencies were found in the Iberian Peninsula (3.98% in Portugal and 3.85% in Spain), dropping to 2.88% in France and showing a less well defined SW-NW gradient. Furthermore, we have tested the agreement between haplotype groups and binary markers haplogroups in a random sample of 292 individuals from Northern Portugal. Our results demonstrate that (a) Y-STR haplotype data can be used for wide-scale anthropological approaches disclosing information that has been considered only available through binary markers and (b) forensic use of continental databases needs careful refinement, due to the macro-geographic pattern now evidenced.