Nitric oxide (NO) has important functions in biology and atmospheric chemistry as a toxin, signaling molecule, ozone depleting agent and the precursor of the greenhouse gas nitrous oxide (N2O). Although NO is a potent oxidant, and was available on Earth earlier than oxygen, it is unclear whether NO can be used by microorganisms for growth. Anaerobic ammonium-oxidizing (anammox) bacteria couple nitrite reduction to ammonium oxidation with NO and hydrazine as intermediates, and produce N2 and nitrate. Here, we show that the anammox bacterium Kuenenia stuttgartiensis is able to grow in the absence of nitrite by coupling ammonium oxidation to NO reduction, and produce only N2. Under these growth conditions, the transcription of proteins necessary for NO generation is downregulated. Our work has potential implications in the control of N2O and NO emissions from natural and manmade ecosystems, where anammox bacteria contribute significantly to N2 release to the atmosphere. We hypothesize that microbial NO-dependent ammonium oxidation may have existed on early Earth.