The paper's first author is Dr Daniel Thomas, a New Zealander who is a postdoctoral fellow at the University of Cape Town, South Africa.
His recent Otago doctorate was supervised by Associate Prof Ewan Fordyce, who heads the Otago University geology department.
Prof Fordyce, who also contributed to the paper, said it had long been believed that penguins thrived by adapting to increasingly cold conditions, including in the now largely ice-covered Antarctic.
This region, which had earlier been semi-tropical, became glaciated about 34 million years ago.
However, the paper points out that, much earlier, about 49 million years ago, penguins lived in much warmer conditions, when some ocean surface temperatures were about 25degC.
And it was at that stage that penguins evolved a key heat-retention mechanism that effectively pre-adapted them to thrive in later, much colder, conditions, including in the Antarctic.
It seemed ''counterintuitive'' for such mechanisms to evolve at a time of global warmth, but researchers suspected that the evolutionary change occurred then ''to allow penguins to forage for food in cool depths, far below the warm surface waters'', Prof Fordyce said.
Faced with a ''constant threat from hypothermia'' in deep, cold waters, penguins had developed a ''counter-current heat exchanger'', which managed the flow of blood along the wing and significantly improved heat retention and energy efficiency.
Wings were used to help propel the birds through the water.
Prof Fordyce said grooves in fossilised wing bones showed evidence of this mechanism.
By the mechanism, warmer blood that was being moved out to the wings was also used to heat the cooler blood coming back from the wings before it re-entered the penguin body core.
Dr Thomas was a ''very, very good researcher'' and the study highlighted the ''power of fossils'' to show how animals had evolved, Prof Fordyce said.