Recent fossil discoveries from New Zealand have revealed a remarkably diverse assemblage of Paleocene stem group penguins. Here, we add to this growing record by describing nine new penguin specimens from the late Paleocene (upper Teurian local stage; 55.5–59.5Ma) Moeraki Formation of the South Island, New Zealand. The largest specimen is assigned to a new species, Kumimanu fordycei sp. nov., that may have been the largest penguin ever to have lived. Allometric regressions based on humerus length and humerus head width of extant penguins yield mean estimates of a live body mass in the range of 159.4 kg (95% CI: 143.4 kg–179.6kg) and 148.7 kg (95% CI: 143.4kg–180.0kg), respectively, for Kumimanu fordycei. A second new species, Petradyptes stonehousei gen. et sp. nov., is represented by five specimens and was slightly larger than the extant emperor penguin Aptenodytes forsteri. Two small humeri represent an additional smaller unnamed penguin species. Parsimony and Bayesian phylogenetic analyses recover Kumimanu and Petradyptes crownward of the early Paleocene mainland NZ taxa Waimanu and Muriwaimanu, but stemward of the Chatham Island taxon Kupoupou. These analyses differ, however, in the placement of these two taxa relative to Sequiwaimanu, Crossvallia, and Kaiika. The massive size and placement of Kumimanu fordycei close to the root of the penguin tree provide additional support for a scenario in which penguins reached the upper limit of sphenisciform body size very early in their evolutionary history, while still retaining numerous plesiomorphic features of the flipper.