When free-living organisms evolve into symbiotic organisms (parasites, commensals, or mutualists), their bodyplan is often dramatically modified as a consequence. The present work pertains to the study of this process in a group of marine obligate symbiotic worms, the Myzostomida. These are mainly ectocommensals and are only associated with echinoderms, mostly crinoids. Their usual textbook status as a class of the Annelida is generally accepted, although recent molecular phylogenetic studies have raised doubts on their relationships with other metazoans, and the question of their status remains open. Here, we reconstruct the evolution of their bodyplans by mapping 14 external morphological characters (analyzed using scanning electron microscopy) onto molecular phylogenies using maximum parsimony (MP) and maximum likelihood (ML) optimality criteria. Rooted MP, ML, and Bayesian phylogenetic trees were obtained by analyzing the nucleotide sequences of cytochrome oxidase subunit I, 18S rDNA, and 16S rDNA genes, separately and in combination. Representatives of 34 species distributed among seven extant genera were investigated. Our character evolution analyses, combined with recent ontogenetic and ultrastructural evidence, indicate that the organism at the base of the myzostome tree would have had six body segments and five pairs of polychaete-type parapodia, and that two lineages emerged from it: one comprising parasites, with large females and dwarf males, which gave rise to the extant Pulvinomyzostomum and Endomyzostoma species, and a second lineage comprising simultaneously hermaphroditic ectocommensals, from which all other extant myzostome taxa probably evolved.