The SOS response comprises a set of cellular functions aimed at preserving bacterial cell viability in front of DNA injuries. The SOS network, negatively regulated by the LexA protein, is found in many bacterial species that have not suffered major reductions in their gene contents, but presents distinctly divergent LexA-binding sites across the Bacteria domain. In this article, we report the identification and characterization of an imported multiple gene cassette in the Gamma Proteobacterium Pseudomonas putida that encodes a LexA protein, an inhibitor of cell division (SulA), an error-prone polymerase (DinP) and the alpha subunit of DNA polymerase III (DnaE). We also demonstrate that these genes constitute a DNA damage-inducible operon that is regulated by its own encoded LexA protein, and we establish that the latter is a direct derivative of the Gram-positive LexA protein. In addition, in silico analyses reveal that this multiple gene cassette is also present in many Proteobacteria families, and that both its gene content and LexA-binding sequence have evolved over time, ultimately giving rise to the lexA lineage of extant Gamma Proteobacteria.