The complete 36,487 bp sequence of plasmid plca36 from Lactobacillus casei Zhang was determined. Plca36 contains 44 predicted coding regions, and to 23 of them functions could be assigned. For the first time, we identified a relBE toxin-antitoxin (TA) locus in a Lactobacillus genus, perhaps indicating a potential role for plca36 in host survival under extreme nutritional stress. A region encoding a cluster of conjugation genes (tra) was also identified. The cluster showed high similarity and co-linearity with tra regions of pWCFS103 and pMRC01 from Lactobacillus plantarum and Lactococcus lactis, respectively. Comparative gene analysis revealed that plasmids from the genus Lactobacillus may have contributed to the environmental adaptation mainly by providing carbohydrate and amino acid transporters. In addition, two chromosome-encoded relBE systems in Lactobacillus johnsonii and Lactobacillus gasseri were identified.