The allelic variability at six Y-chromosome-specific polymorphisms (YAP, DYS19, DYS389-I, DYS390, DYS391, and DYS392) was used to generate male-specific haplotypes in 333 males representing 12 population samples from the region around the Mediterranean sea. Extreme interindividual variation was observed, as more than 160 distinct Y-chromosome variants could be defined as six-locus haplotypes. Concomitant with this high variability, low levels of population genetic structure were observed. In particular, a "core" of populations directly facing the north and the east of the Mediterranean basin, from the Middle East to the Italian Peninsula, was found to be genetically undifferentiated. This observation, supported by a reanalysis of Y-specific binary polymorphisms in the same populations, suggests that at least part of the male-specific gene pools of these populations has either a very recent common origin (that could be related with the Neolithic demic diffusion hypothesis), and/or that gene flow has played a significant role in shaping the patterns of genetic variability in this region. In agreement with both hypotheses, we found that the spatial distribution of DYS392 alleles revealed a marked differentiation between the East and the West of the Mediterranean area. Through the analysis of microsatellite variation, the time to the most recent common ancestor (TMRCA) of the YAP(+) sublineage 4 has been estimated. The estimations, based on two different data sets, turn out to be quite recent (7,000-11,000 YBP), suggesting that this lineage may have been first introduced into Southern Europe through Neolithic migrations from the Middle East.