The early Miocene is one of the least understood intervals in cetacean evolution. A new early Miocene dolphin described here, Papahu taitapu, gen. et sp. nov. (family incertae sedis, Cetacea, Odontoceti), is from the Kaipuke Formation (21.7–18.7 Ma) of North West Nelson, New Zealand. The holotype of Papahu taitapu includes a skull with an open mesorostral canal, a broad-based rostrum (broken anteriorly), two pairs of premaxillary foramina, a slight bilateral asymmetry at the antorbital notches, a slight intertemporal constriction exposing the temporal fossa and the lateral wall of the braincase in dorsal view, and single-rooted (and probably homodont) teeth. The periotic has an inflated, spherical pars cochlearis and an anterior process with the anterointernal sulcus and a recurved lateral sulcus well developed. The skull size indicates a body length of about 2 m. Papahu taitapu plots cladistically in a cluster of archaic dolphins variously referred to as Platanistoidea or as stem Odontoceti. It matches no family described so far, but cladistic relationships for comparable odontocetes are not yet resolved enough to justify family placement.