AbstractNitrogen (N2) fixation in oligotrophic surface waters is the main source of new nitrogen to the ocean1 and has a key role in fuelling the biological carbon pump2. Oceanic N2 fixation has been attributed almost exclusively to cyanobacteria, even though genes encoding nitrogenase, the enzyme that fixes N2 into ammonia, are widespread among marine bacteria and archaea3–5. Little is known about these non-cyanobacterial N2 fixers, and direct proof that they can fix nitrogen in the ocean has so far been lacking. Here we report the discovery of a non-cyanobacterial N2-fixing symbiont, ‘Candidatus Tectiglobus diatomicola’, which provides its diatom host with fixed nitrogen in return for photosynthetic carbon. The N2-fixing symbiont belongs to the order Rhizobiales and its association with a unicellular diatom expands the known hosts for this order beyond the well-known N2-fixing rhizobia–legume symbioses on land6. Our results show that the rhizobia–diatom symbioses can contribute as much fixed nitrogen as can cyanobacterial N2 fixers in the tropical North Atlantic, and that they might be responsible for N2 fixation in the vast regions of the ocean in which cyanobacteria are too rare to account for the measured rates.