The Mediterranean region has been characterised by a number of pre‐historical and historical demographic events whose legacy on the current genetic landscape is still a matter of debate. In order to investigate the degree of population structure across the Mediterranean, we have investigated Y chromosome variation in a large dataset of Mediterranean populations, 11 of which are first described here. Our analyses identify four main clusters in the Mediterranean that can be labelled as North Africa, Arab, Central‐East and West Mediterranean. In particular, Near Eastern samples tend to separate according to the presence of Arab Y chromosome lineages, suggesting that the Arab expansion played a major role in shaping the current genetic structuring within the Fertile Crescent.