The Cenozoic Pelagornithidae, or pseudotoothed birds, are characterized by unique bony projections along the cutting edges of the beak. These birds were previously known from late Paleocene to Pliocene fossil sites and some species reached wingspans up to 6.4 metres. Here we describe a partial skeleton of a small-sized pelagornithid from the early Paleocene of New Zealand. Protodontopteryx ruthae, gen. et sp. nov. is the oldest record of the clade, the smallest known species, and the first pre-Eocene pelagornithid from the Southern Hemisphere. The skull of the new species exhibits the characteristic pelagornithid morphology, but the postcranial skeleton distinctly differs from other pelagornithids and various plesiomorphic features indicate that it is the earliest-diverging representative of the Pelagornithidae. The much stouter humerus suggests that the new species was less adapted to sustained soaring than previously known pelagornithids. Pseudoteeth therefore evolved before pelagornithids became highly specialized gliders. Unlike the giant Neogene pelagornithid species, which presumably were skimmers, early Paleocene pelagornithids are likely to have targeted selected prey items and may have been predominantly piscivorous. The new species furthermore suggests that pelagornithids evolved in the Southern Hemisphere and documents a very early radiation of neornithine seabirds, which may have been triggered by changes in marine ecosystems around the K-Pg boundary. We finally comment on the unusual preservation of the fossil, which may be due to the activity of marine scavengers.