Nitrate and nitrite are the most preferable electron acceptors in the absence of molecular oxygen. In the γ-proteobacterium Escherichia coli, nitrate and nitrite respiration is regulated by two homologous transcription factors, NarL and NarP. Although this regulatory system was a subject of intensive research for more than 20 years, many key issues, including the structure of the NarL-binding site, are still unclear. Comparative genomics analysis showed that only NarP is responsible for regulation in most γ-proteobacteria. The NarP regulon was studied in ten genomes. Although its structure considerably differs among some genomes, the mechanism regulating the nitrate and nitrite reduction genes is highly conserved. A correlation was observed between the evolutionary changes in the nitrate and nitrite respiration system and the relevant regulatory system. Potential NarP-binding sites were found upstream of the gene for the global regulator FNR and the sydAB, mdh, and sucAB aerobic metabolism genes. It was assumed on the basis of this evidence that the role of NarP in regulating respiration changed during evolution. In total, 35 new operons were assigned to the generalized NarP regulon. Autoregulation of the narQP operon was suggested for bacteria of the family Vibrionaceae.