Symbiotic relationships on coral reefs involving benthic hosts other than scleractinian corals have been poorly investigated. The hydroid Pteroclava krempfi is a widespread species known to be mainly associated with alcyonacean octocorals in the Indo-Pacific. In the present study, P. krempfi was discovered in association with octocorals of the genus Antillogorgia (Gorgoniidae) at two localities in the Caribbean Sea (St. Eustatius in the eastern Caribbean and Bocas del Toro in the western part), updating its host range with an additional genus and family. The Caribbean specimens showed no morphological differences and the shape of their polyps was consistent with the original P. krempfi description. A multi-locus phylogeny reconstruction of the P. krempfi species complex based on both mitochondrial and nuclear loci revealed three separate molecular clades. Two of them were composed of P. krempfi associated with the families Plexauridae and Alcyoniidae from the Maldives, whereas a new highly supported molecular lineage included all Caribbean specimens of P. krempfi associated with the family Gorgoniidae. These three divergent molecular clades represent distinct cryptic taxa within the P. krempfi species complex, in which the main interspecific difference consists of their host families.