Ancient genomes provide a tool to investigate the genetic basis of adaptations in extinct organisms. However, the identification of species-specific fixed genetic variants requires the analysis of genomes from multiple individuals. Moreover, the long-term scale of adaptive evolution coupled with the short-term nature of traditional time series data has made it difficult to assess when different adaptations evolved. Here, we analyze 23 woolly mammoth genomes, including one of the oldest known specimens at 700,000 years old, to identify fixed derived non-synonymous mutations unique to the species and to obtain estimates of when these mutations evolved. We find that at the time of its origin, the woolly mammoth had already acquired a broad spectrum of positively selected genes, including ones associated with hair and skin development, fat storage and metabolism, and immune system function. Our results also suggest that these phenotypes continued to evolve during the last 700,000 years, but through positive selection on different sets of genes. Finally, we also identify additional genes that underwent comparatively recent positive selection, including multiple genes related to skeletal morphology and body size, as well as one gene that may have contributed to the small ear size in Late Quaternary woolly mammoths.