Although the fossil record of beaked whales (Cetacea, Odontoceti, Ziphiidae) is continuously improving, the geological age of new taxa is often poorly constrained. Based on a partial cranium from deep seafloor deposits off Galicia, Spain, we describe a new species of the stem beaked whale genus Beneziphius, B. cetariensis sp. nov. The latter differs from the type species B. brevirostris in the larger size, the rostrum being proportionally longer, the premaxillae being longer than the maxillae at the apex of the rostrum, the left premaxillary sac fossa being transversely concave, and the ascending process of the premaxilla reaching the vertical. Considering that the stratigraphic context of deep-sea deposits off the Iberian Peninsula is not precisely known, we provisionally propose an extended, middle Miocene to early Pliocene interval for the geological age of B. cetariensis. Nonetheless, the palynological analysis of sediment sampled from cavities in the cranium of the holotype of B. brevirostris, discovered during the second part of the nineteenth century in inland deposits of Antwerp (north of Belgium), yield an early to mid-Serravallian age (13.2–12.8 Ma, late middle Miocene). B. brevirostris is thus the oldest described species of the “Messapicetus clade”, a large clade of stem ziphiids in which most species are dated from the late Miocene. The description of the Galician species B. cetariensis broadens the biogeographic distribution of Beneziphius and confirms the strong ziphiid faunal affinities between the eastern coast of the North Atlantic and the southern margin of the North Sea Basin.