Ancient DNA research indicates that, to a first order of approximation, the genomes of present-day Europeans comprise ancestries from three major groups of people: 1) indigenous Mesolithic hunter-gatherers; 2) Near Eastern early farmers; 3) Steppe pastoralists. However, the detailed genetic history of any given area is always much more complex, calling for more focused and local-scale studies. One such interesting but so far understudied region is modern-day Ukraine, which borders with Central European Poland, Slovakia and Hungary to the west while Southern Ukraine is part of the vast Eurasian Steppe. As such, the area has been in the path of several migrating groups. Here we present novel genome-wide shotgun sequencing data from 91 individuals from Neolithic to early modern Ukraine, associated mostly with the Bronze Age Belozerska, Luzhitska and Vysotska cultures, the Iron Age Thracian Hallstatt, Scythian and Chernyakhov periods, the medieval Saltiv, Golden Horde and Nogai groups, and early modern Cossacks. The genomes have been sequenced to an average genomic coverage of 0.5x. The ancestry compositions of the individuals are characterised in the context of previously published modern and ancient samples from Ukraine and Eurasia in general, and interpreted in the context of archaeological and historical information. The results show considerable genetic variability within groups of individuals with the same cultural association (especially within Scythian- and Saltiv-associated individuals), as well as between different groups and time periods. Genetic influences from the Near East, the Western steppe, and East Asia can be inferred.