Two independent isolates of the gut commensal Lactobacillus johnsonii were sequenced. These isolates belonged to the same clonal lineage and differed mainly by a 40.8-kb prophage, LJ771, belonging to the Sfi11 phage lineage. LJ771 shares close DNA sequence identity with Lactobacillus gasseri prophages. LJ771 coexists as an integrated prophage and excised circular phage DNA, but phage DNA packaged into extracellular phage particles was not detected. Between the phage lysin gene and attR a likely mazE ("antitoxin")/pemK ("toxin") gene cassette was detected in LJ771 but not in the L. gasseri prophages. Expressed pemK could be cloned in Escherichia coli only together with the mazE gene. LJ771 was shown to be highly stable and could be cured only by coexpression of mazE from a plasmid. The prophage was integrated into the methionine sulfoxide reductase gene (msrA) and complemented the 5' end of this gene, creating a protein with a slightly altered N-terminal sequence. The two L. johnsonii strains had identical in vitro growth and in vivo gut persistence phenotypes. Also, in an isogenic background, the presence of the prophage resulted in no growth disadvantage.