Bacteria use small molecules to assess the density and identity of nearby organisms and formulate a response. This process, called quorum sensing (QS), commonly regulates bioluminescence, biofilm formation, and virulence. Vibrio harveyi have three described QS circuits. Each involves the synthesis of a molecule that regulates phosphorylation of its cognate receptor kinase. Each receptor exchanges phosphate with a common phosphorelay protein, LuxU, which ultimately regulates bioluminescence. Here, we show that another small molecule, nitric oxide (NO), participates in QS through LuxU. V. harveyi display a NO concentration-dependent increase in bioluminescence that is regulated by an hnoX gene. We demonstrate that H-NOX is a NO sensor and NO/H-NOX regulates phosphorylation of a kinase that transfers phosphate to LuxU. This study reveals the discovery of a fourth QS pathway in V. harveyi and suggests that bacteria use QS to integrate not only the density of bacteria but also other diverse information about their environment into decisions about gene expression.