Oxygen minimum zones (OMZs) are marine regions characterized by a sharp oxycline overlying an anoxic zone where O₂ concentration is below the detection limit (<10 nM). OMZs contain less than 1% of total seawater in volume, but contribute up to 30% of oceanic fixed nitrogen loss through anaerobic microbial processes occurring in their anoxic zones. Nitrite oxidation is also detected in OMZs, although it is regarded as an aerobic process and all known marine nitrite-oxidizing bacteria (NOB) are aerobes. We explored the OMZ NOB using metagenomics, and recovered two nearly complete genomes of NOB from Pacific OMZs. They represented two novel species, both of which differed at the species level from all published (draft) genomes of NOB from oxic seawater. These novel NOB were present in all three major OMZs and were most abundant in anoxic zones, which is consistent with the detection of higher nitrite oxidation rates in anoxic zones than in oxic seawater. In addition, we provide the first direct experimental evidence of anaerobic nitrite oxidation, and its full inhibition by oxygen, in anoxic zones where the novel NOB were present. The responses of nitrite oxidation to both nitrite and oxygen varied along the redox gradient, implying that diverse assemblages of NOB use different mechanisms for nitrite oxidation in different redox layers. Implementing anaerobic nitrite oxidation in a biogeochemical model decreased the estimate of nitrogen loss by up to ~60%, suggesting the importance of this previously ignored nitrogen cycle process.