In recent years, the recognition sequence of the SOS repressor LexA protein has been identified for several bacterial clades, such as the Gram-positive, green non-sulfur bacteria and Cyanobacteria phyla, or the 'Alphaproteobacteria', 'Deltaproteobacteria' and 'Gammaproteobacteria' classes. Nevertheless, the evolutionary relationship among these sequences and the proteins that recognize them has not been analysed. Fibrobacter succinogenes is an anaerobic Gram-negative bacterium that branched from a common bacterial ancestor immediately before the Proteobacteria phylum. Taking advantage of its intermediate position in the phylogenetic tree, and in an effort to reconstruct the evolutionary history of LexA-binding sequences, the F. succinogenes lexA gene has been isolated and its product purified to identify its DNA recognition motif through electrophoretic mobility assays and footprinting experiments. After comparing the available LexA DNA-binding sequences with the F. succinogenes one, reported here, directed mutagenesis of the F. succinogenes LexA-binding sequence and phylogenetic analyses of LexA proteins have revealed the existence of two independent evolutionary lanes for the LexA recognition motif that emerged from the Gram-positive box: one generating the Cyanobacteria and 'Alphaproteobacteria' LexA-binding sequences, and the other giving rise to the F. succinogenes and Myxococcus xanthus ones, in a transitional step towards the current 'Gammaproteobacteria' LexA box. The contrast between the results reported here and the phylogenetic data available in the literature suggests that, some time after its emergence as a distinct bacterial class, the 'Alphaproteobacteria' lost its vertically received lexA gene, but received later through lateral gene transfer a new lexA gene belonging to either a cyanobacterium or a bacterial species closely related to this phylum. This constitutes the first report based on experimental evidence of lateral gene transfer in the evolution of a gene governing such a complex regulatory network as the bacterial SOS system.