Three skeletons collected from the late Oligocene Kokoamu Greensand of New Zealand are among the most complete Paleogene penguins known. These specimens, described here as Kairuku waitaki gen. et sp. nov. and Kairuku grebneffi sp. nov., reveal for the first time the unique proportions of a giant fossil penguin and the morphology of many key elements of the stem penguin skeleton associated with underwater flight, including the first reasonably complete sternum, one of only two complete forelimbs and the first described pygostyle. Relative proportions of the trunk, flippers and hindlimbs can now be determined from a single individual, offering insight into the body plan of stem penguins and improved constraints on size estimates for 'giant' taxa. Kairuku is characterized by an elongate, narrow sternum, a short and flared coracoid, an elongate narrow flipper and a robust hindlimb. The pygostyle of Kairuku lacks the derived triangular cross-section seen in extant Spheniscidae, suggesting the rectrices attached in a more typical avian pattern and the tail may have lacked the propping function utilized by living penguins. New materials described here, along with restudy of previously described specimens, resolves several long-standing phylogenetic, biogeographic and taxonomic issues stemming from the inadequate comparative material of several of the first-named fossil penguin species. An array of partial associated skeletons from the Eocene-Oligocene of New Zealand historically referred to Palaeeudyptes antarcticus or Palaeeudyptes sp. are recognized as at least five distinct species: Palaeeudyptes antarcticus, Palaeeudyptes marplesi, Kairuku waitaki, Kairuku grebneffi and an unnamed Burnside Formation species