We describe leg bones of a giant penguin from the mid-Paleocene Waipara Greensand of New Zealand. The specimens were found at the type locality of Waimanu manneringi and together with this species they constitute the oldest penguin fossils known to date. Tarsometatarsus dimensions indicate a species that reached the size of Anthropornis nordenskjoeldi, one of the largest known penguin species. Stem group penguins therefore attained a giant size very early in their evolution, with this gigantism existing for more than 30 million years. The new fossils are from a species that is phylogenetically more derived than Waimanu, and the unexpected coexistence of Waimanu with more derived stem group Sphenisciformes documents a previously unknown diversity amongst the world’s oldest penguins. The characteristic tarsometatarsus shape of penguins evolved early on, and the significant morphological disparity between Waimanu and the new fossil conflicts with recent Paleocene divergence estimates for penguins, suggesting an older, Late Cretaceous, origin.