The evolutionarily recent dispersal of Anatomically Modern Humans (AMH) out of Africa and across Eurasia provides an opportunity to study rapid genetic adaptation to multiple new environments. Genomic analyses of modern human populations have detected limited signals of strong selection such as hard sweeps, but genetic admixture between populations is capable of obscuring these patterns and is well known in recent human history, such as during the Bronze Age4. Here we show that ancient human genomic datasets contain multiple genetic signatures of strong selection including 57 hard sweeps, many with strong associations with cold adaptation. Similar genetic signatures of adaptation are also observed in adaptively-introgressed archaic hominin loci, as well as modern Arctic human groups. Consistent targets include the regulation of fat storage, skin physiology, cilia function and neural development; with multiple associations to modern western diseases. The spatiotemporal patterns of the hard sweeps allow reconstruction of early AMH population dispersals, and reveal a prolonged period of genetic adaptation (~80-50,000 years) following their initial out of Africa movement, before a rapid spread across Eurasia reaching as far as Australia.