Penguins are the only extant family of flightless diving birds. They currently comprise at least 18 species, distributed from polar to tropical environments in the Southern Hemisphere. The history of their diversification and adaptation to these diverse environments remains controversial. We used 22 new genomes from 18 penguin species to reconstruct the order, timing, and location of their diversification, to track changes in their thermal niches through time, and to test for associated adaptation across the genome. Our results indicate that the penguin crown-group originated during the Miocene in New Zealand and Australia, not in Antarctica as previously thought, and that Aptenodytes is the sister group to all other extant penguin species. We show that lineage diversification in penguins was largely driven by changing climatic conditions and by the opening of the Drake Passage and associated intensification of the Antarctic Circumpolar Current (ACC). Penguin species have introgressed throughout much of their evolutionary history, following the direction of the ACC, which might have promoted dispersal and admixture. Changes in thermal niches were accompanied by adaptations in genes that govern thermoregulation and oxygen metabolism. Estimates of ancestral effective population sizes (N-e) confirm that penguins are sensitive to climate shifts, as represented by three different demographic trajectories in deeper time, the most common (in 11 of 18 penguin species) being an increased N-e between 40 and 70 kya, followed by a precipitous decline during the Last Glacial Maximum. The latter effect is most likely a consequence of the overall decline in marine productivity following the last glaciation.