Symbiotic associations between microbes and invertebrates have resulted in some of the most unusual physiological and morphological adaptations that have evolved in the animal world. We document a new symbiosis between marine polychaetes of the genus Osedax and members of the bacterial group Oceanospirillales, known for heterotrophic degradation of complex organic compounds. These organisms were discovered living on the carcass of a grey whale at 2891 m depth in Monterey Canyon, off the coast of California. The mouthless and gutless worms are unique in their morphological specializations used to obtain nutrition from decomposing mammalian bones. Adult worms possess elaborate posterior root-like extensions that invade whale bone and contain bacteriocytes that house intracellular symbionts. Stable isotopes and fatty acid analyses suggest that these unusual endosymbionts are likely responsible for the nutrition of this locally abundant and reproductively prolific deep-sea worm.