The Cucuteni-Trypillia complex (CTC) flourished in eastern Europe for over two millennia (5100–2800 BCE) from the end of the Neolithic to the Early Bronze Age. Its vast distribution area encompassed modern-day eastern Romania, Moldova and western/central Ukraine. Due to a lack of existing burials throughout most of this time, only little is known about the people associated with this complex and their genetic composition. Here, we present genome-wide data generated from the skeletal remains of four females that were excavated from two Late CTC sites in Moldova (3500–3100 BCE). All individuals carried a large Neolithic-derived ancestry component and were genetically more closely related to Linear Pottery than to Anatolian farmers. Three of the specimens also showed considerable amounts of steppe-related ancestry, suggesting influx into the CTC gene-pool from people affiliated with, for instance, the Ukraine Mesolithic. The latter scenario is supported by archaeological evidence. Taken together, our results confirm that the steppe component arrived in eastern Europe farming communities maybe as early as 3500 BCE. In addition, they are in agreement with the hypothesis of ongoing contacts and gradual admixture between incoming steppe and local western populations.