Bacteriocins are a large and functionally diverse family of toxins found in all major lineages of Bacteria. Colicins, those bacteriocins produced by Escherichia coli, serve as a model system for investigations of bacteriocin structure–function relationships, genetic organization, and their ecological role and evolutionary history. Colicin expression is often dependent on host regulatory pathways (such as the SOS system), is usually confined to times of stress, and results in death of the producing cells. This study investigates the role of the SOS system in mediating this unique form of toxin expression. A comparison of all the sequenced enteric bacteriocin promoters reveals that over 75% are regulated by dual, overlapping SOS boxes, which serve to bind two LexA repressor proteins. Furthermore, a highly conserved poly-A motif is present in both of the binding sites examined, indicating enhanced affinity of the LexA protein for the binding site. The use of gene expression analysis and deletion mutations further demonstrates that these unique LexA cooperative binding regions result in a fine tuning of bacteriocin production, limiting it to times of stress. These results suggest that the evolution of dual SOS boxes elegantly accomplishes the task of increasing the amount of toxin produced by a cell while decreasing the rate of uninduced production, effectively reducing the cost of colicin production. This hypothesis may explain why such a promoter motif is present at such high frequencies in natural populations of bacteriocin-producing enteric bacteria.