We investigated the regulation of the S10 ribosomal protein (r-protein) operon among members of the gamma subdivision of the proteobacteria, which includes Escherichia coli. In E. coli, this 11-gene operon is autogenously controlled by r-protein L4. This regulation requires specific determinants within the untranslated leader of the mRNA. Secondary structure analysis of the S10 leaders of five enterobacteria (Salmonella typhimurium, Citrobacter freundii, Yersinia enterocolitica, Serratia marcescens, and Morganella morganii) and two nonenteric members of the gamma subdivision (Haemophilus influenzae and Vibrio cholerae) shows that these foreign leaders share significant structural homology with the E. coli leader, particularly in the region which is critical for L4-mediated autogenous control in E. coli. Moreover, these heterologous leaders produce a regulatory response to L4 oversynthesis in E. coli. Our results suggest that an E. coli-like L4-mediated regulatory mechanism may operate in all of these species. However, the mechanism is not universally conserved among the gamma subdivision members, since at least one, Pseudomonas aeruginosa, does not contain the required S10 leader features, and its leader cannot provide the signals for regulation by L4 in E. coli. We speculate that L4-mediated autogenous control developed during the evolution of the gamma branch of proteobacteria.