Colicins, a class of antimicrobial compounds produced by bacteria, are thought to be important mediators of intra- and interspecific interactions, and are a significant factor in maintaining microbial diversity. Colicins B and M are among the most common colicins produced by Escherichia coli, and are usually encoded adjacently on the same plasmid. In this study, the characterization of a collection of E. coli isolated from Australian vertebrates revealed that a significant fraction of colicin BM strains lack an intact colicin B activity gene. The colicin B and M gene region was sequenced in 60 strains and it was found (with one exception) that all plasmids lacking an intact colicin B activity gene have an identical colicin gene structure, possessing a complete colicin B immunity gene and a 130 bp remnant of the B activity gene. A phylogenetic analysis of the colicin M and B operons and characterization of the plasmids suggested that ColBM plasmids with a truncated B activity gene have evolved on at least three separate occasions. Colicin B immunity was found to be non-functional in strains that have lost colicin B activity, and colicin M was still produced despite the absence of the SOS box believed to regulate its production in colicin BM strains. The presence of a remnant of the microcin V operon next to the truncated colicin B activity gene indicated that these plasmids evolved as a consequence of gene transfer between colicin BM and microcin V plasmids. We suggest that these transfer events most likely involved the transfer of some microcin V genes and associated virulence factors onto ColBM plasmids.