Scleractinian corals create three-dimensional reefs that provide sheltered refuges, facilitate sediment accumulation, and enhance colonization of encrusting fauna. While heterogeneous coral habitats can harbor high levels of biodiversity, their effect on the community composition within nearby sediments remains unclear, particularly in the deep sea. Sediment macrofauna from deep-sea coral habitats (Lophelia pertusa) and non-coral, background sediments were examined at three sites in the northern Gulf of Mexico (VK826, VK906, MC751, 350–500 m depth) to determine whether macrofaunal abundance, diversity, and community composition near corals differed from background soft-sediments. Macrofaunal densities ranged from 26 to 125 individuals 32 cm−2 and were significantly greater near coral versus background sediments only at VK826. Of the 86 benthic invertebrate taxa identified, 16 were exclusive to near-coral habitats, while 14 were found only in background sediments. Diversity (Fisher’s α) and evenness were significantly higher within near-coral sediments only at MC751 while taxon richness was similar among all habitats. Community composition was significantly different both between near-coral and background sediments and among the three primary sites. Polychaetes numerically dominated all samples, accounting for up to 70% of the total individuals near coral, whereas peracarid crustaceans were proportionally more abundant in background sediments (18%) than in those near coral (10%). The reef effect differed among sites, with community patterns potentially influenced by the size of reef habitat. Taxon turnover occurred with distance from the reef, suggesting that reef extent may represent an important factor in structuring sediment communities near L. pertusa. Polychaete communities in both habitats differed from other Gulf of Mexico (GOM) soft sediments based on data from previous studies, and we hypothesize that local environmental conditions found near L. pertusa may influence the macrofaunal community structure beyond the edges of the reef. This study represents the first assessment of L. pertusa-associated sediment communities in the GOM and provides baseline data that can help define the role of transition zones, from deep reefs to soft sediments, in shaping macrofaunal community structure and maintaining biodiversity; this information can help guide future conservation and management activities.