In this study, the genetic relationship and the population structure of western Mediterranean basin native sheep breeds are investigated, analyzing Maghrebian, Central Italian, and Venetian sheep with a highly informative microsatellite markers panel. The phylogeographical analysis, between breeds’ differentiation level (Wright’s fixation index), gene flow, ancestral relatedness measured by molecular coancestry, genetic distances, divergence times estimates and structure analyses, were revealed based on the assessment of 975 genotyped animals. The results unveiled the past introduction and migration history of sheep in the occidental Mediterranean basin since the early Neolithic. Our findings provided a scenario of three westward sheep migration phases fitting properly to the westward Neolithic expansion argued by zooarcheological, historical and human genetic studies.