Nitric oxide (NO) signaling in animals controls processes such as smooth muscle relaxation and neurotransmission by activation of soluble guanylate cyclase (sGC). Prokaryotic homologues of the sGC heme domain, called H-NOX domains, have been identified and are generally found in a predicted operon in conjunction with a histidine kinase. Here, we show that an H-NOX protein (SO2144) from Shewanella oneidensis directly interacts with the sensor histidine kinase (SO2145), binds NO in a 5-coordinate complex similar to mammalian sGC, and in that form inhibits the activity of a histidine kinase (SO2145). We also describe the first account of NO formation by S. oneidensis under anaerobic growth conditions derived from nitrate and nitrite. These observations suggest that the S. oneidensis H-NOX and histidine kinase pair function as part of a novel two-component signaling pathway that is responsive to NO formation from higher nitrogen oxides used as electron acceptors when oxygen is low and thereby functioning as an environmental sensor.