We investigated the genetic diversity of symbiotic bacteria associated with two newly discovered species of Osedax from Monterey Canyon, CA, at 1,017-m (Osedax Monterey Bay sp. 3 “rosy” [Osedax sp. MB3]) and 381-m (Osedax Monterey Bay sp. 4 “yellow collar”) depths. Quantitative PCR and clone libraries of 16S rRNA gene sequences identified differences in the compositions and abundances of bacterial phylotypes associated with the newly discovered host species and permitted comparisons between adult Osedax frankpressi and juveniles that had recently colonized whalebones implanted at 2,891 m. The newly discovered Osedax species hosted Oceanospirillales symbionts that are related to Gammaproteobacteria associated with the previously described O. frankpressi and Osedax rubiplumus (S. K. Goffredi, V. J. Orphan, G. W. Rouse, L. Jahnke, T. Embaye, K. Turk, R. Lee, and R. C. Vrijenhoek, Environ. Microbiol. 7:1369–1378, 2005). In addition, Osedax sp. MB3 hosts a diverse and abundant population of additional bacteria dominated by Epsilonproteobacteria. Ultrastructural analysis of symbiont-bearing root tissues verified the enhanced microbial diversity of Osedax sp. MB3. Root tissues from the newly described host species and O. frankpressi all exhibited collagenolytic enzyme activity, which covaried positively with the abundance of symbiont DNA and negatively with mean adult size of the host species. Members of this unusual genus of bone-eating worms may form variable associations with symbiotic bacteria that allow for the observed differences in colonization and success in whale fall environments throughout the world’s oceans.