Microbial communities inhabiting gorgonian corals are believed to benefit their hosts through nutrient provision and chemical defence; yet much remains to be learned about their phylogenetic uniqueness and cultivability. Here, we determined the prokaryotic community structure and distinctiveness in the gorgonian Eunicella labiata by Illumina sequencing of 16S rRNA genes from gorgonian and seawater metagenomic DNA. Furthermore, we used a ‘plate-wash’ methodology to compare the phylogenetic diversity of the ‘total’ gorgonian bacteriome and its ‘cultivatable’ fraction. With 1016 operational taxonomic units (OTUs), prokaryotic richness was higher in seawater than in E. labiata where 603 OTUs were detected, 68 of which were host-specific. Oceanospirillales and Rhodobacterales predominated in the E. labiata communities. One Oceanospirillales OTU, classified as Endozoicomonas, was particularly dominant, and closest relatives comprised exclusively uncultured clones from other gorgonians. We cultivated a remarkable 62% of the bacterial symbionts inhabiting E. labiata: Ruegeria, Sphingorhabdus, Labrenzia, other unclassified Rhodobacteraceae, Vibrio and Shewanella ranked among the 10 most abundant genera in both the cultivation-independent and dependent samples. In conclusion, the E. labiata microbiome is diverse, distinct from seawater and enriched in (gorgonian)-specific bacterial phylotypes. In contrast to current understanding, many dominant E. labiata symbionts can, indeed, be cultivated.