We sequenced genomes from a ∼7,000 year old early farmer from Stuttgart in Germany, an ∼8,000 year old hunter-gatherer from Luxembourg, and seven ∼8,000 year old hunter-gatherers from southern Sweden. We analyzed these data together with other ancient genomes and 2,345 contemporary humans to show that the great majority of present-day Europeans derive from at least three highly differentiated populations: West European Hunter-Gatherers (WHG), who contributed ancestry to all Europeans but not to Near Easterners; Ancient North Eurasians (ANE), who were most closely related to Upper Paleolithic Siberians and contributed to both Europeans and Near Easterners; and Early European Farmers (EEF), who were mainly of Near Eastern origin but also harbored WHG-related ancestry. We model these populations’ deep relationships and show that EEF had ∼44% ancestry from a “Basal Eurasian” lineage that split prior to the diversification of all other non-African lineages.