Nitrogen-fixing (diazotrophic) microorganisms regulate productivity in diverse ecosystems; however, the identities of diazotrophs are unknown in many oceanic environments. Using single-cell-resolution nanometer secondary ion mass spectrometry images of 15N incorporation, we showed that deep-sea anaerobic methane-oxidizing archaea fix N2, as well as structurally similar CN-, and share the products with sulfate-reducing bacterial symbionts. These archaeal/bacterial consortia are already recognized as the major sink of methane in benthic ecosystems, and we now identify them as a source of bioavailable nitrogen as well. The archaea maintain their methane oxidation rates while fixing N2 but reduce their growth, probably in compensation for the energetic burden of diazotrophy. This finding extends the demonstrated lower limits of respiratory energy capable of fueling N2 fixation and reveals a link between the global carbon, nitrogen, and sulfur cycles.