The Late Oligocene is a period of high penguin diversity, following major changes in the marine environment at the Eocene/Oligocene boundary and prior to the emergence of crown penguins in the Miocene. Historically, a large morphological gap existed between the most crownward Platydyptes among the Oligocene penguins from New Zealand and the Early Miocene stem penguins such as Palaeospheniscus and Eretiscus from South America. Here we describe a new species that contributes to filling this gap. Pakudyptes hakataramea gen. et sp. nov. is the earliest tiny penguin, overlapping in size with the smallest extant species, the little penguin Eudyptula minor. Its distinctive combination of a well-developed proximal end of the humerus and a rather archaic elbow joint provides clues to the evolution of penguin wings. Phylogenetic analysis indicates that penguin wings evolved rapidly from the Late Oligocene to the Early Miocene, together with the acquisition of morphofunctional and hydrodynamical characteristics that enable the excellent swimming ability of modern penguins. As an indicator of aquatic adaptation, bone microanatomy also shows a comparable structure to that of Eudyptula. The appearance of the smallest body size and the evolution of modern wings may have led to the ecological diversity of modern penguins, which confirms the importance of Zealandia in penguin evolution.