The osteophagous worm Osedax (Annelida: Siboglinidae) colonizes vertebrate bones in deep-sea environments globally. Osedax bioerosion of modern bones suggests a potentially destructive agent in the marine vertebrate fossil record, but the dearth of published reports of abundant Osedax traces suggests an uncertain taphonomic influence of this organism. This study reports Osedax traces (Osspecus boreholes, pockmarks and collapsed galleries) in an Oligocene baleen whale (Cetacea: Eomysticetidae) from New Zealand, which constitute the first record of fossil Osedax traces from the southern hemisphere. Some Osedax traces are cross-cut by linear biogenic scrape marks, implying that sharks or bony fish fed upon Osedax worms, a process which compounds or potentially accelerates worm-inflicted damage to vertebrate bones in marine environments.