Cold-water corals provide critical habitats for a multitude of marine species, but are understudied relative to tropical corals. Primnoa pacifica is a cold-water coral prevalent throughout Alaskan waters, while another species in the genus, Primnoa resedaeformis, is widely distributed in the Atlantic Ocean. This study examined the V4-V5 region of the 16S rRNA gene after amplifying and pyrosequencing bacterial DNA from samples of these species. Key differences between the two species’ microbiomes included a robust presence of bacteria belonging to the Chlamydiales order in most of the P. pacifica samples, whereas no more than 2% of any microbial community from P. resedaeformiscomprised these bacteria. Microbiomes of P. resedaeformis exhibited higher diversity than those of P. pacifica, and the two species largely clustered separately in a principal coordinate analysis. Comparison of P. resedaeformis microbiomes from samples collected in two submarine canyons revealed a significant difference between locations. This finding mirrored significant genetic differences among the P. resedaeformis from the two canyons based upon population genetic analysis of microsatellite loci. This study presents the first report of microbiomes associated with these two coral species.