Rickettsiales are a lineage of obligate intracellular Alphaproteobacteria, encompassing important human pathogens, manipulators of host reproduction, and mutualists. Here we report the discovery of a novel Rickettsiales bacterium associated with Paramecium, displaying a unique extracellular lifestyle, including the ability to replicate outside host cells. Genomic analyses show that the bacterium possesses a higher capability to synthesise amino acids, compared to all investigated Rickettsiales. Considering these observations, phylogenetic and phylogenomic reconstructions, and re-evaluating the different means of interaction of Rickettsiales bacteria with eukaryotic cells, we propose an alternative scenario for the evolution of intracellularity in Rickettsiales. According to our reconstruction, the Rickettsiales ancestor would have been an extracellular and metabolically versatile bacterium, while obligate intracellularity would have evolved later, in parallel and independently, in different sub-lineages. The proposed new scenario could impact on the open debate on the lifestyle of the last common ancestor of mitochondria within Alphaproteobacteria.