Priapulus caudatus (phylum Priapulida) is a benthic marine predatory worm with a cosmopolitan distribution. In its digestive tract we detected symbiotic bacteria that were consistently present in specimens collected over eight years from three sites at the Swedish west coast. Based on their 16S rRNA gene sequence, these symbionts comprise a novel genus of the order Rickettsiales (Alphaproteobacteria). Electron microscopy and fluorescence in situ hybridization (FISH) identified them as extracellular, elongate bacteria closely associated with the microvilli, for which we propose the name ‘Candidatus Tenuibacter priapulorum’. Within Rickettsiales, they form a phylogenetically well-defined, family-level clade with uncultured symbionts of marine, terrestrial, and freshwater arthropods. Cand. Tenuibacter priapulorum expands the host range of this candidate family from Arthropoda to the entire Ecdysozoa, which may indicate an evolutionary adaptation of this bacterial group to the microvilli-lined guts of the Ecdysozoa.