Holosporales are an alphaproteobacterial lineage encompassing bacteria obligatorily associated with multiple diverse eukaryotes. For most representatives, little is known on the interactions with their hosts. In this study, we characterized a novel Holosporales symbiont of the ciliate Paramecium polycaryum. This bacterium inhabits the host cytoplasm, frequently forming quite large aggregates. Possibly due to such aggregates, host cells sometimes displayed lethal division defects. The symbiont was also able to experimentally stably infect another Paramecium polycaryum strain. The bacterium is phylogenetically related with symbionts of other ciliates and diplonemids, forming a putatively fast-evolving clade within the family Holosporaceae. Similarly to many close relatives, it presents a very small genome (<600 kbp), and, accordingly, a limited predicted metabolism, implying a heavy dependence on Paramecium, thanks also to some specialized membrane transporters. Characterized features, including the presence of specific secretion systems, are overall suggestive of a mild parasitic effect on the host. From an evolutionary perspective, a potential ancestral trend towards pronounced genome reduction and possibly linked to parasitism could be inferred, at least among fast-evolving Holosporaceae, with some lineage-specific traits. Interestingly, similar convergent features could be observed in other host-associated lineages, in particular Rickettsiales among Alphaproteobacteria.