Here, we report a comprehensive description of the stable associations between two Paramecium species (P. nephridiatum and P. caudatum) and their cytoplasmic bacterial endosymbiont Pseudolyticum multiflagellatum. These spindle-like, rod-shaped, non-motile peritrichous bacteria demonstrate significant phenotypic polymorphism. Considering the differences in bacterial morphology and host species, several scientific groups have previously described these endosymbionts as distinct species. Our study provides brand-new molecular data, which allows us to unify earlier descriptions and determine the phylogenetic position of this endosymbiont as a member of the family “Ca. Midichloriaceae” (Rickettsiales). The distinguishing feature of this bacterium is the presence of a highly refractive granule in its cytoplasm, well detectable with differential interference contrast (DIC) microscopy. The protein nature of these peculiar inclusion bodies is considered. The other endosymbiont, “Ca. Megaira venefica”, co-inhabiting the cytoplasm of the studied P. nephridiatum strains, also displayed polymorphism, rounded forms being infected with phages.