We present the first ancient DNA data from the Pre-Pottery Neolithic of Mesopotamia (Southeastern Turkey and Northern Iraq), Cyprus, and the Northwestern Zagros, along with the first data from Neolithic Armenia. We show that these and neighboring populations were formed through admixture of pre-Neolithic sources related to Anatolian, Caucasus, and Levantine hunter-gatherers, forming a Neolithic continuum of ancestry mirroring the geography of West Asia. By analyzing Pre-Pottery and Pottery Neolithic populations of Anatolia, we show that the former were derived from admixture between Mesopotamian-related and local Epipaleolithic-related sources, but the latter experienced additional Levantine-related gene flow, thus documenting at least two pulses of migration from the Fertile Crescent heartland to the early farmers of Anatolia.