The range of substrates that the bone-eating marine worm Osedax is able to consume has important implications for its evolutionary history, especially its potential link to the rise of whales. Once considered a whale specialist, recent work indicates that Osedax consumes a wide range of vertebrate remains, including whale soft tissue and the bones of mammals, birds, and fishes. Traces resembling those produced by living Osedax have now been recognized for the first time in Oligocene whale teeth and fish bones from deep-water strata of the Makah, Pysht and Lincoln Creek formations in western Washington State, USA. The specimens were acid etched from concretions and details of the borehole morphology were investigated using micro-computed tomography. Together with previously published Osedax traces from this area, our results show that by Oligocene time Osedax was able to colonize the same range of vertebrate remains that it consumes today and had a similar diversity of root morphologies. This supports the view that a generalist ability to exploit vertebrate bones may be an ancestral trait of Osedax.