Nitrate and nitrite are efficient respiratory oxidants for anaerobic growth. In Escherichia coli, the homologous nitrate reductase (Nar) two-component regulatory systems NarX–NarL and NarQ–NarP collaborate to control anaerobic respiratory gene expression in response to nitrate and nitrite. Several other species classified in the γ and β subdivisions of the proteobacteria contain only a single Nar two-component regulatory pair. This raises questions concerning the physiology of anaerobic respiration as well as the evolution, function and cross-regulation of two-component regulatory systems. Here, I focus on the sensor histidine kinases NarX and NarQ, and present a comparison of the deduced NarX and NarQ primary sequences from a broad sampling of proteobacteria. This comparison defines shared features, including a large central region of unknown function that appears to be unique to this family of sensor kinases. I then consider the phylogenetic distribution of narX and narQ genes in relation to anaerobic respiratory enzyme repertoire and physiological function. One noteworthy observation is that narXL genes are specifically associated with the structural genes for membrane-bound nitrate reductase, narGHJI, whereas organization and linkage of the narQ and narP genes is quite variable. I conclude with some speculative thoughts on the evolutionary and functional divergence of the NarX–NarL and NarQ–NarP regulatory systems. Overall, this analysis aims to provide a basis for future hypothesis and experimentation in this area.