New protein function is thought to evolve mostly by gene duplication and divergence. Here we present phylogenetic evidence that the multifunctional protein Fis of the gamma proteobacterial species derived from the COOH-terminal domain of an ancestral alpha proteobacterial NtrC transcriptional regulatory protein. All of the known enterobacterial fis genes are preceded by an open reading frame, named yhdG, that is highly similar to nifR3, a gene that forms an operon with ntrC in several alpha proteobacterial species. Thus, we propose that yhdG and fis were acquired by a lineage ancestral to the gamma proteobacteria in a single horizontal gene transfer event, and later diverged to their present functions.