We report fossil traces of Osedax, a genus of siboglinid annelids that consume the skeletons of sunken vertebrates on the ocean floor, from early-Late Cretaceous (approx. 100 Myr) plesiosaur and sea turtle bones. Although plesiosaurs went extinct at the end-Cretaceous mass extinction (66 Myr), chelonioids survived the event and diversified, and thus provided sustenance for Osedax in the 20 Myr gap preceding the radiation of cetaceans, their main modern food source. This finding shows that marine reptile carcasses, before whales, played a key role in the evolution and dispersal of Osedax and confirms that its generalist ability of colonizing different vertebrate substrates, like fishes and marine birds, besides whale bones, is an ancestral trait. A Cretaceous age for unequivocal Osedax trace fossils also dates back to the Mesozoic the origin of the entire siboglinid family, which includes chemosynthetic tubeworms living at hydrothermal vents and seeps, contrary to phylogenetic estimations of a Late Mesozoic–Cenozoic origin (approx. 50–100 Myr).