Prions are self-propagating protein aggregates that act as protein-based elements of inheritance in fungi. Although prevalent in eukaryotes, prions have not been identified in bacteria. Here we found that a bacterial protein, transcription terminator Rho of Clostridium botulinum (Cb-Rho), could form a prion. We identified a candidate prion-forming domain (cPrD) in Cb-Rho and showed that it conferred amyloidogenicity on Cb-Rho and could functionally replace the PrD of a yeast prion-forming protein. Furthermore, its cPrD enabled Cb-Rho to access alternative conformations in Escherichia coli-a soluble form that terminated transcription efficiently and an aggregated, self-propagating prion form that was functionally compromised. The prion form caused genome-wide changes in the transcriptome. Thus, Cb-Rho functions as a protein-based element of inheritance in bacteria, suggesting that the emergence of prions predates the evolutionary split between eukaryotes and bacteria.