Sheep were among the first domesticated animals, but their demographic history is little understood. Here we analyzed nuclear polymorphism and mitochondrial data (mtDNA) from ancient central and west Anatolian sheep dating from Epipaleolithic to late Neolithic, comparatively with modern-day breeds and central Asian Neolithic/Bronze Age sheep (OBI). Analyzing ancient nuclear data, we found that Anatolian Neolithic sheep (ANS) are genetically closest to present-day European breeds relative to Asian breeds, a conclusion supported by mtDNA haplogroup frequencies. In contrast, OBI showed higher genetic affinity to present-day Asian breeds. These results suggest that the east-west genetic structure observed in present-day breeds had already emerged by 6000 BCE, hinting at multiple sheep domestication episodes or early wild introgression in southwest Asia. Furthermore, we found that ANS are genetically distinct from all modern breeds. Our results suggest that European and Anatolian domestic sheep gene pools have been strongly remolded since the Neolithic.