Marine annelid worms of the genus Osedax exploit sunken vertebrate bones for food. To date, the named species occur on whale or other mammalian bones, and it is argued that Osedax is a whale-fall specialist. To assess whether extant Osedax species could obtain nutrition from non-mammalian resources, we deployed teleost bones and calcified shark cartilage at approximately 1000 m depth for five months. Although the evidence from shark cartilage was inconclusive, the teleost bones hosted three species of Osedax, each of which also lives off whalebones. This suggests that rather than being a whale-fall specialist, Osedax has exploited and continues to exploit a variety of food sources. The ability of Osedax to colonize and to grow on fishbone lends credibility to a hypothesis that it might have split from its siboglinid relatives to assume the bone-eating lifestyle during the Cretaceous, well before the origin of marine mammals.