Prions are self-propagating protein aggregates formed by specific proteins that can adopt alternative folds. Prions were discovered as the cause of the fatal transmissible spongiform encephalopathies in mammals, but prions can also constitute nontoxic protein-based elements of inheritance in fungi and other species. Prion propagation has recently been shown to occur in bacteria for more than a hundred cell divisions, yet a fraction of cells in these lineages lost the prion through an unknown mechanism. Here, we investigate prion propagation in single bacterial cells as they divide using microfluidics and fluorescence microscopy. We show that the propagation occurs in two distinct modes. In a fraction of the population, cells had multiple small visible aggregates and lost the prion through random partitioning of aggregates to one of the two daughter cells at division. In the other subpopulation, cells had a stable large aggregate localized to the pole; upon division the mother cell retained this polar aggregate and a daughter cell was generated that contained small aggregates. Extending our findings to prion domains from two orthologous proteins, we observe similar propagation and loss properties. Our findings also provide support for the suggestion that bacterial prions can form more than one self-propagating state. We implement a stochastic version of the molecular model of prion propagation from yeast and mammals that recapitulates all the observed single-cell properties. This model highlights challenges for prion propagation that are unique to prokaryotes and illustrates the conservation of fundamental characteristics of prion propagation.