The chapter describes the exceptional symbiotic associations formed between the ciliate Paramecium and Holospora, highly infectious bacteria residing in the host nuclei. Holospora and Holospora-like bacteria (Alphaproteobacteria) are characterized by their ability for vertical and horizontal transmission in host populations, a complex biphasic life cycle, and pronounced preference for host species and colonized cell compartment. These bacteria are obligate intracellular parasites; thus, their metabolic repertoire is dramatically reduced. Nevertheless, they perform complex interactions with the host ciliate. We review ongoing efforts to unravel the molecular adaptations of these bacteria to their unusual lifestyle and the host’s employment in the symbiosis. Furthermore, we summarize current knowledge on the genetic and genomic background of Paramecium–Holospora symbiosis and provide insights into the ecological and evolutionary consequences of this interaction. The diversity and occurrence of symbioses between ciliates and Holospora-like bacteria in nature is discussed in connection with transmission modes of symbionts, host specificity and compatibility of the partners. We aim to summarize 50 years of research devoted to these symbiotic systems and conclude trying to predict some perspectives for further studies.