The Neolithic transition was a dynamic time in European prehistory of cultural, social, and technological change. Although this period has been well explored in central Europe using ancient nuclear DNA, its genetic impact on northern and eastern parts of this continent has not been as extensively studied. To broaden our understanding of the Neolithic transition across Europe, we analyzed eight ancient genomes: six samples (four to ~1- to 4-fold coverage) from a 3,500 year temporal transect (~8,300–4,800 calibrated years before present) through the Baltic region dating from the Mesolithic to the Late Neolithic and two samples spanning the Mesolithic-Neolithic boundary from the Dnieper Rapids region of Ukraine. We find evidence that some hunter-gatherer ancestry persisted across the Neolithic transition in both regions. However, we also find signals consistent with influxes of non-local people, most likely from northern Eurasia and the Pontic Steppe. During the Late Neolithic, this Steppe-related impact coincides with the proposed emergence of Indo-European languages in the Baltic region. These influences are distinct from the early farmer admixture that transformed the genetic landscape of central Europe, suggesting that changes associated with the Neolithic package in the Baltic were not driven by the same Anatolian-sourced genetic exchange.