Bacteria are recognized as an important part of the total biology of shallow-water corals. Studies of shallow-water corals suggest that associated bacteria may benefit the corals by cycling carbon, fixing nitrogen, chelating iron, and producing antibiotics that protect the coral from other microbes. Cold-water or deep-sea corals have a fundamentally different ecology due to their adaptation to cold, dark, high-pressure environments and as such have novel microbiota. The goal of this study was to characterize the microbial associates of Lophelia pertusa in the northeastern Gulf of Mexico. This is the first study to collect the coral samples in individual insulated containers and to preserve coral samples at depth in an effort to minimize thermal shock and evaluate the effects of environmental gradients on the microbial diversity of samples. Molecular analysis of bacterial diversity showed a marked difference between the two study sites, Viosca Knoll 906/862 (VK906/862) and Viosca Knoll 826 (VK826). The bacterial communities from VK826 were dominated by a variety of unknown mycoplasmal members of the Tenericutes and Bacteroidetes, whereas the libraries from VK906/862 were dominated by members of the Proteobacteria. In addition to novel sequences, the 16S rRNA gene clone libraries revealed many bacterial sequences in common between Gulf of Mexico Lophelia corals and Norwegian fjord Lophelia corals, as well as shallow-water corals. Two Lophelia-specific bacterial groups were identified: a cluster of gammaproteobacteria related to sulfide-oxidizing gill symbionts of seep clams and a group of Mycoplasma spp. The presence of these groups in both Gulf and Norwegian Lophelia corals indicates that in spite of the geographic heterogeneity observed in Lophelia-associated bacterial communities, there are Lophelia-specific microbes.