Species in the genus Paramuricea are among the most common corals in deep waters (>200 m) of the Gulf of Mexico. Paramuricea spp. increase habitat heterogeneity and provide substrate for numerous faunal associates, including ophiuroids that occur on the majority of coral colonies. In light of the Deepwater Horizon oil spill in the Gulf of Mexico, it has become apparent that there is a critical need for data on population dynamics within this genus. To date, at least one species of Paramuricea (P. biscaya) is known to be negatively impacted by the spill. Using remotely operated vehicles from 2009 to 2011, we documented the density and size frequency distributions of Paramuricea across 21 sites at depths of 250–2500 m. Molecular barcoding (mtCOI+igr+MutS) was used to delineate species boundaries among the specimens collected. Results suggested that seven haplotypes are present in the Gulf, and appear to be partially segregated by depth [(type H: <260 m) (type E: 278–445 m) (type A: 443–541 m) (types B1–B3: 800–2600 m)]. Densities of Paramuricea spp. determined by ROV surveys were mapped onto high-resolution bathymetric data, which confirmed the corals' preference for topographic highs composed of hard substrata. At any one site, densities ranged from 0.043±0.01 (VK906, 380 m) to 1.18±0.81 colonies/m2 (GC852, 1410 m). Mortality and recruitment rates were estimated from size-frequency data combined with estimated growth rates. Mortality rate decreased with size, from approximately 20% and 70% in new recruits of Paramuricea B3 and P. biscaya respectively, to less than 10% in colonies over 40 cm in both species. Recruitment rates were estimated from less than one to over 30 individuals per year per site, but patterns in size-frequency histograms suggest that this process is highly variable at the different sites and at different times. These data illustrate that populations of the slow-growing Paramuricea species are sparsely distributed and exhibit low recruitment rates, making them highly susceptible to anthropogenic threats.