Microbial enzymes often occur as distinct variants that share the same substrate but differ in substrate affinity, sensitivity to environmental conditions, or phylogenetic ancestry. Determining where variants occur in the environment helps identify thresholds that constrain microbial cycling of key chemicals, including the greenhouse gas nitrous oxide (NO). To understand the enzymatic basis of NO cycling in the ocean, we mined metagenomes to characterize genes encoding bacterial nitrous oxide reductase (NosZ) catalyzing NO reduction to N. We examined data sets from diverse biomes but focused primarily on those from oxygen minimum zones where NO levels are often elevated. With few exceptions, marine nosZ data sets were dominated by 'atypical' clade II gene variants. Atypical nosZ has been associated with low oxygen, enhanced NO affinity, and organisms lacking enzymes for complete denitrification, i.e., non-denitrifiers. Atypical nosZ often occurred in metagenome-assembled genomes (MAGs) with nitrate or nitrite respiration genes, although MAGs with genes for complete denitrification were rare. We identified atypical nosZ in several taxa not previously associated with NO consumption, in addition to known NO-associated groups. The data suggest that marine environments generally select for high NO-scavenging ability across diverse taxa and have implications for how NO concentration may affect NO removal rates.