The genomic landscape of Stone Age Europe was shaped by multiple migratory waves and population replacements, but different regions do not all show similar patterns. To refine our understanding of the population dynamics before and after the dawn of the Neolithic, we generated and analyzed genomic sequence data from human remains of 56 individuals from the Mesolithic, Neolithic, and Eneolithic across Central and Eastern Europe. We found that Mesolithic European populations formed a geographically widespread isolation-by-distance zone ranging from Central Europe to Siberia, which was already established 10,000 years ago. We found contrasting patterns of population continuity during the Neolithic transition: people around the lower Dnipro Valley region, Ukraine, showed continuity over 4000 years, from the Mesolithic to the end of the Neolithic, in contrast to almost all other parts of Europe where population turnover drove this cultural change, including vast areas of Central Europe and around the Danube River. Genome-wide sequencing of 56 ancient hunter-gatherer and early farmer individuals from Stone Age Central and Eastern Europe reveals striking population continuity in the east in contrast to central Europe that displays extensive admixture.