Penguins (Sphenisciformes) inhabit some of the most extreme environments on Earth. The 60+ Myr fossil record of penguins spans an interval that witnessed dramatic shifts in Cenozoic ocean temperatures and currents, indicating a long interplay between penguin evolution and environmental change. Perhaps the most celebrated example is the successful Late Cenozoic invasion of glacial environments by crown clade penguins. A major adaptation that allows penguins to forage in cold water is the humeral arterial plexus, a vascular counter-current heat exchanger (CCHE) that limits heat loss through the flipper. Fossil evidence reveals that the humeral plexus arose at least 49 Ma during a 'Greenhouse Earth' interval. The evolution of the CCHE is therefore unrelated to global cooling or development of polar ice sheets, but probably represents an adaptation to foraging in subsurface waters at temperate latitudes. As global climate cooled, the CCHE was key to invasion of thermally more demanding environments associated with Antarctic ice sheets.