The remarkable geographical situation of the Mediterranean region, located between Europe, Africa, and Asia, with numerous migratory routes, has made this area a crucible of cultures. Studying the Y-chromosome variability is a very performant tool to explore the genetic ancestry and evaluate scenarios that may explain the current Mediterranean gene pool. Here, six Mediterranean populations, including three Balearic Islands (Ibiza, Majorca, and Minorca) and three Southern Italian regions (Catanzaro, Cosenza, and Reggio di Calabria) were typed using 23 Y-STR loci and up to 39 Y-SNPs and compared to geographically targeted key reference populations to explore their genetic relationship and provide an overview of Y-chromosome variation across the Mediterranean basin. Pairwise R genetic distances calculated with STRs markers and Y-haplogroups mirror the West to East geographic distribution of European and Asian Mediterranean populations, highlighting the North-South division of Italy, with a higher Eastern Mediterranean component in Southern Italian populations. In contrast, the African populations from the Southern coast of the Mediterranean clustered separately. Overall, these results support the notion that migrations from Magna Graecia or the Byzantine Empire, which followed similar Neolithic and post-Neolithic routes into Southern Italy, may have contributed to maintaining and/or reinforcing the Eastern Mediterranean genetic component in Southern Italian populations.