"Candidatus Fokinia solitaria" is an obligate intracellular endosymbiont of a unicellular eukaryote, a ciliate of the genus Paramecium. Here, we present the genome sequence of this bacterium and subsequent analysis. Phylogenomic analysis confirmed the previously reported positioning of the symbiont within the "Candidatus Midichloriaceae" family (order Rickettsiales), as well as its high sequence divergence from other members of the family, indicative of fast sequence evolution. Consistently with this high evolutionary rate, a comparative genomic analysis revealed that the genome of this symbiont is the smallest of the Rickettsiales to date. The reduced genome does not present flagellar genes, nor the pathway for the biosynthesis of lipopolysaccharides (present in all the other so far sequenced members of the family "Candidatus Midichloriaceae") or genes for the Krebs cycle (present, although not always complete, in Rickettsiales). These results indicate an evolutionary trend toward a stronger dependence on the host, in comparison with other members of the family. Two alternative scenarios are compatible with our results; "Candidatus Fokinia solitaria" could be either a recently evolved, vertically transmitted mutualist, or a parasite with a high host-specificity.