Nitrogen fixation in the surface ocean impacts global marine nitrogen bioavailability and thus microbial primary productivity. Until now, cyanobacterial populations have been viewed as the main suppliers of bioavailable nitrogen in this habitat. Although PCR amplicon surveys targeting the nitrogenase reductase gene have revealed the existence of diverse non-cyanobacterial diazotrophic populations, subsequent quantitative PCR surveys suggest that they generally occur in low abundance. Here, we use state-of-the-art metagenomic assembly and binning strategies to recover nearly one thousand non-redundant microbial population genomes from the TARA Oceans metagenomes. Among these, we provide the first genomic evidence for non-cyanobacterial diazotrophs inhabiting surface waters of the open ocean, which correspond to lineages within the Proteobacteria and, most strikingly, the Planctomycetes. Members of the latter phylum are prevalent in aquatic systems, but have never been linked to nitrogen fixation previously. Moreover, using genome-wide quantitative read recruitment, we demonstrate that the discovered diazotrophs were not only widespread but also remarkably abundant (up to 0.3% of metagenomic reads for a single population) in both the Pacific Ocean and the Atlantic Ocean northwest. Our results extend decades of PCR-based gene surveys, and substantiate the importance of heterotrophic bacteria in the fixation of nitrogen in the surface ocean.