Over the last decade, publications on deep-sea corals have tripled. Most attention has been paid to Lophelia pertusa, a globally distributed scleractinian coral that creates critical three-dimensional habitat in the deep ocean. The bacterial community associated with L. pertusa has been previously described by a number of studies at sites in the Mediterranean Sea, Norwegian fjords, off Great Britain, and in the Gulf of Mexico (GOM). However, use of different methodologies prevents direct comparisons in most cases. Our objectives were to address intra-regional variation and to identify any conserved bacterial core community. We collected samples from three distinct colonies of L. pertusa at each of four locations within the western Atlantic: three sites within the GOM and one off the east coast of the United States. Amplicon libraries of 16S rRNA genes were generated using primers targeting the V4–V5 hypervariable region and 454 pyrosequencing. The dominant phylum was Proteobacteria (75–96%). At the family level, 80–95% of each sample was comprised of five groups: Pirellulaceae, Pseudonocardiaceae, Rhodobacteraceae, Sphingomonadaceae, and unclassified Oceanospirillales. Principal coordinate analysis based on weighted UniFrac distances showed a clear distinction between the GOM and Atlantic samples. Interestingly, the replicate samples from each location did not always cluster together, indicating there is not a strong site-specific influence. The core bacterial community, conserved in 100% of the samples, was dominated by the operational taxonomic units of genera Novosphingobium and Pseudonocardia, both known degraders of aromatic hydrocarbons. The sequence of another core member, Propionibacterium, was also found in prior studies of L. pertusa from Norway and Great Britain, suggesting a role as a conserved symbiont. By examining more than 40,000 sequences per sample, we found that GOM samples were dominated by the identified conserved core sequences, whereas open Atlantic samples had a much higher proportion of locally consistent bacteria. Further, predictive functional profiling highlights the potential for the L. pertusa microbiome to contribute to chemoautotrophy, nutrient cycling, and antibiotic production.