As you can see in the pedigree on the right side, birds and reptiles are close relatives. Actually, you could think that birds are closer related to mammals because this two classes have a lot of common characteristics. For example, birds and mammals are endothermic animals while reptiles are ectothermic. How did scientists come to the conclusion that birds are closer related to reptiles?
They discovered a fossil which is called archeopteryx, it is the connecting link between reptiles and birds. This ancient bird from Jurassic period has characteristics of reptiles, for example a jaw with tooth, as well as characteristics of birds like feathers and wings. So, the archeopteryx is the earliest known progenitor of all birds and also of penguins.
There were already the first flightless birds at Cretaceous period, but penguins do not derive from them. Surprisingly, penguins have common ancestors with birds that can fly. This was diagnosed in many analyses. In morphological studies penguins share some traits of bones (e.g. in skull or pelvis) with for example loons and grebes. Because of this findings a relationship between this birds is supposed. In a study which compared proteins (transferrin, ovalbumin and penalbumin) penguins are declared as closely related to albatrosses, loons, grebes and herons. As in other animals, too, there are still different opinions between authors and a definite result about the relationship of penguins to other birds is not given yet. Different opinions base on different methods the researchers used for their analyses.
The oldest known penguins are called waimanu (in Maori "wai" means water and "manu" means bird). Fossils of the two species Waimanu tuatahi and Waimanu manneringi were found in New Zealand and 58 and 61 million years old. So, they lived closely to the Cretaceous-Tertiary boundary (estimated 66 million years ago). Their size was approximately 80 cm (M. tuatahi) and 1 m (M. manneringi).
But there were found other penguin fossils of extinct species which were huge, significantly taller than all extant penguin species! They could nearly reach a size of an average grown-up human being!
However, it is suggested that penguins derive from birds that were able to dive and fly. Because of their ability to fly they had to be quite small. So how the penguin evolution leads to these huge penguins?
It is supposed that penguins derive from small auks that were still able to dive AND fly. Their size was comparable to the size of the Little Blue Penguin. But when the ability to fly was lost and they were more adapted to aquatic flight, the size did not matter anymore and bigger penguins could develop. The wings became flat and stiff flippers which allow penguins to swim fastly and versatilely. This is one possible idea of penguin evolution.
Unfortunately, the large penguins are extinct. A reason could be that there was a strong food competition with marine mammals.
There is a debate between researchers about the local origin of penguins. One opinion is that the early penguins lived in Antarctica and due to a global cooling they left it. Another hypothesis is that penguins lived in Australia and New Zealand originally, this is supported by an analysis of fossils which were found in many regions where recent penguins live. But fossils from Antarctica are still lacking.
It is assumed that ancestral penguins were due to their size able to disperse via ocean currents to South America. There the genus Banded Penguins developed. A group of penguins which arrived there were split into Galapagos and Humboldt Penguins later, they presumably were dispersed by the Humboldt current. Another group were distributed by the westward Brazil-Benguela current and were split into Magellanic (Tierra del Fuego, Southern Chile and Argentina) and African Penguins (Southern Africa). But this is only one example of genera development. Today, penguins are divided into 6 genera and 18 species.
You see, the relationships and origins are not clear yet. Depending on the methods the results differ. That is why there is more research necessary to clarify the penguin evolution definitely.
Cracraft, J. (1981). Toward a phylogenetic classification of the recent birds of the world (Class Aves). The Auk, 681-714.
Ho, C. Y. K., Prager, E. M., Wilson, A. C., Osuga, D. T., & Feeney, R. E. (1976). Penguin evolution: protein comparisons demonstrate phylogenetic relationship to flying aquatic birds. Journal of Molecular Evolution, 8(3), 271-282.
Slack, K. E., Jones, C. M., Ando, T., Harrison, G. A., Fordyce, R. E., Arnason, U., & Penny, D. (2006). Early penguin fossils, plus mitochondrial genomes, calibrate avian evolution. Molecular Biology and Evolution, 23(6), 1144-1155.
Ksepka, D. T., Bertelli, S., & Giannini, N. P. (2006). The phylogeny of the living and fossil Sphenisciformes (penguins). Cladistics, 22(5), 412-441.
Baker, A. J., Pereira, S. L., Haddrath, O. P., & Edge, K. A. (2006). Multiple gene evidence for expansion of extant penguins out of Antarctica due to global cooling. Proceedings of the Royal Society B: Biological Sciences, 273(1582), 11-17.
Boessenkool, S., Austin, J. J., Worthy, T. H., Scofield, P., Cooper, A., Seddon, P. J., & Waters, J. M. (2009). Relict or colonizer? Extinction and range expansion of penguins in southern New Zealand. Proceedings of the Royal Society B: Biological Sciences, 276(1658), 815-821.