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.