Symbiosis is a diverse and complex phenomenon requiring diverse model systems. The obligate relationship between a monophyletic group of Euplotes species (“clade B”) and the betaproteobacteria Polynucleobacter and “Candidatus Protistobacter” is among the best-studied in ciliates, and provides a framework to investigate symbiont replacements. Several other Euplotes-bacteria relationships exist but are less understood, such as the co-dependent symbiosis between Euplotes magnicirratus (which belongs to “clade A”) and the alphaproteobacterium “Candidatus Devosia euplotis”. Here we describe a new Devosia inhabiting the cytoplasm of a strain of Euplotes harpa, a clade B species that usually depends on Polynucleobacter for survival. The novel bacterial species, “Candidatus Devosia symbiotica”, is closely related to the symbiont of E. magnicirratus, casting a different light on the history of bacteria colonizing ciliates of this genus. The two Devosia species may have become symbionts independently or as the result of a symbiont exchange between hosts, in either case replacing a previous essential bacterium in E. harpa. Alternatively, both may be remnants of an ancient symbiotic relationship between Euplotes and Devosia, in which case Polynucleobacter and “Ca. Protistobacter” are recent invaders. Either way, symbiont replacement between bacteria belonging to different classes must be evoked to explain this fascinating system.