The clinal pattern observed for the distribution of Y-chromosome lineages in Europe is not always reflected at a geographically smaller scale. Six hundred and sixty-three male samples from the 18 administrative districts of Portugal were typed for 25 Y-chromosome biallelic and 15 microsatellite markers, in order to assess the degree of substructuring of male lineage distribution. Haplogroup frequency distributions, Analysis of Molecular Variance (AMOVA) and genetic distance analyses at both Y-SNP and Y-STR levels revealed a general genetic homogeneity of Portuguese sub-populations. The traditional division of the country in north, central and south, which is usually considered in studies addressing questions of the genetic variation distribution in Portugal, was not reflected in the Y-haplotype distribution. Instead, just one sub-region (Alentejo) stood out due to the presence of high diversity levels and a higher number of different lineages, at higher frequencies than in other regions. These results are reconciled with the historical evidence available, assuming that from prehistorical times down to the end of the medieval period this region harboured the most diverse groups of people and, because of economic depression, remained relatively isolated from recent homogenisation movements. The finding of a broadly homogeneous background for the Portuguese population has vast repercussions in forensic, epidemiological and association studies.