Although molecular-based phylogenetic studies of hosts and their associates are increasingly common in the literature, no study to date has examined the hypothesis of coevolutionary process between hosts and commensals in the marine environment. The present work investigates the phylogenetic relationships among 16 species of obligate symbiont marine worms (Myzostomida) and their echinoderm hosts (Crinoidea) in order to estimate the phylogenetic congruence existing between the two lineages. The combination of a high species diversity in myzostomids, their host specificity, their wide variety of lifestyles and body shapes, and millions years of association, raises many questions about the underlying mechanisms triggering their diversification. The phylogenetic relationships, inferred using a three-genes dataset (18S rDNA, 16S rDNA, and COI) and two-genes dataset (18S rDNA, and COI) for the myzostomids and crinoids, respectively, were congruent with the literature. The overall congruence between the two phylogenies was statistically significant according to topology-based, distance-based, and data-based approaches: a significant pattern of cophylogeny was found, though not perfect probably resulting from occasional host switches, duplications or extinction events. A minimum of 8 cospeciation events was estimated, which is significantly higher than it would have been expected due to chance alone.