Cold-water corals, like tropical corals, contain diverse and complex microbial communities. Studies have shown that 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, a total of 23 octocoral samples of the family Anthothelidae were collected from Norfolk (n = 12) and Baltimore Canyons (n = 11) off the Mid-Atlantic coast of the United States in August 2012 and May 2013. Sample depths ranged from 401 - 704 meters. DNA was extracted and bacterial communities were sequenced using 454 pyrosequencing with GS FLX Titanium chemistry. Primers targeted the V4-V5 variable region of the 16S rRNA gene. Genetic testing found that the 23 samples comprised three coral species: Anthothela grandiflora, Anthothela sp. and a new genus. The two species of Anthothela shared very similar bacterial communities, in contrast to the new genus, which had a more diverse microbiome, distinct from the rest.