The finding of significant vertebrate remains inside commercial stone blocks is relatively rare. Here we describe a fossil cetacean skull discovered inside two slabs cut from a limestone block of Tortonian (i.e., early late Miocene) age from Menorca (Balearic Islands, Spain); this find represents the third record of a fossil cetacean from this island, as well as the best preserved. Unlike similar cases in the past, the Menorca skull was not extracted mechanically from the stone matrix, being rather imaged by means of computed tomography. The resulting 3D reconstruction of the skull allows us to refer the studied skull to the extant odontocete family Ziphiidae (beaked whales) and sheds light on the morphology of very delicate structures (e.g., the thin pterygoid hamuli and the mesorostral cartilage) that would likely have been destroyed during traditional mechanical preparation. This non-invasive investigation permits detailed osteo-anatomical comparisons between the Menorca specimen and other extinct ziphiids, leading to the referral of the former to the stem beaked whale Messapicetus cf. longirostris. We then review the geographic distribution of fossil remains of Messapicetus, which include other occurrences from Tortonian shelf deposits of southeastern Italy, southern Peru, and Maryland (eastern USA). Early branching beaked whales (including basal members of the so-called "Messapicetus clade") likely dispersed via the Central American Seaway, which allowed a direct communication between the Pacific and Atlantic oceans (including the Mediterranean cul-de-sac) throughout the Miocene.