The study of DNA variation is one of the most promising avenues for learning about the evolutionary and historical past of humans and other species. However, the difficulty associated with obtaining DNA directly from ancient remains have for long kept genomic studies of population history trapped in time; confined to interpreting patterns of modern-day variation without direct historical observations. In this thesis, I outline new approaches for the retrieval, analysis and interpretation of large-scale genomic data from ancient populations, including solutions to overcome problems associated with limited genome coverage, modern-day contamination, temporal differences between samples, and post-mortem DNA damage. I integrate large-scale genomic data sets from ancient remains with modern-day variation to trace the human past; from traits targeted by natural selection in the early ancestors of anatomically modern humans, to their descendants' interbreeding with archaic populations in Eurasia and the spread of agriculture in Europe and Africa. By first reconstructing the earliest population diversification events of early modern humans using a novel large-scale genomic data set from Khoe-San populations in southern Africa, I devise a new approach to search for genomic patterns of selective sweeps in ancestral populations and report evidence for skeletal development as a major target of selection during the emergence of early modern humans. Comparing publicly available genomes from archaic humans, I further find that the distribution of archaic human ancestry in Eurasia is more complex than previously thought. In the first direct genomic study of population structure in prehistoric populations, I demonstrate that individuals associated with farming- and hunter-gatherer complexes in Neolithic Scandinavia were strongly genetically differentiated, and direct comparisons with modern-day populations as well as other prehistoric individuals from Southern Europe suggest that this structure originated from Northward expansion of Neolithic farming populations. Finally, I develop a bioinformatic approach for removing modern-day contamination from large-scale ancient DNA sequencing data, and use this method to reconstruct the complete mitochondrial genome sequence of a Siberian Neandertal that is affected by substantial modern-day contamination.