Cold-water corals, similar to tropical corals, contain diverse and complex microbial assemblages. These bacteria provide essential biological functions within coral holobionts, facilitating increased nutrient utilization and production of antimicrobial compounds. To date, few cold-water octocoral species have been analyzed to explore the diversity and abundance of their microbial associates. For this study, 23 samples of the family Anthothelidae were collected from Norfolk (n = 12) and Baltimore Canyons (n = 11) from the western Atlantic in August 2012 and May 2013. Genetic testing found that these samples comprised two Anthothela species (Anthothela grandiflora and Anthothela sp.) and Alcyonium grandiflorum. DNA was extracted and sequenced with primers targeting the V4-V5 variable region of the 16S rRNA gene using 454 pyrosequencing with GS FLX Titanium chemistry. Results demonstrated that the coral host was the primary driver of bacterial community composition. Al. grandiflorum, dominated by Alteromonadales and Pirellulales had much higher species richness, and a distinct bacterial community compared to Anthothela samples. Anthothela species (A. grandiflora and Anthothela sp.) had very similar bacterial communities, dominated by Oceanospirillales and Spirochaetes. Additional analysis of core-conserved bacteria at 90% sample coverage revealed genus level conservation across Anthothela samples. This core included unclassified Oceanospirillales, Kiloniellales, Campylobacterales, and genus Spirochaeta. Members of this core were previously recognized for their functional capabilities in nitrogen cycling and suggest the possibility of a nearly complete nitrogen cycle within Anthothela species. Overall, many of the bacterial associates identified in this study have the potential to contribute to the acquisition and cycling of nutrients within the coral holobiont.