N2 fixation should be a critical process in the nitrogen-poor surface water of the eastern Mediterranean Sea. Despite favorable conditions, diazotroph abundance and N2 fixation rates remains low for reasons yet explained. The main goal of this study was to investigate the limiting nutrients for diazotrophy in this oligotrophic environment. Hence, we conducted dedicated bottle-microcosms with eastern Mediterranean Sea water that were supplemented with mono and polysaccharides as well as inorganic nitrogen and phosphorous. Our results indicate that the diazotrophic community expressing nifH was primarily represented by heterotrophic Proteobacteria. N2 fixation and heterotrophic bacterial activity increased up-to tenfold following two days of dark incubations, once seawater was supplemented with organic carbon substrate in the form of glucose (monosaccharides) or gum-xanthan (polysaccharide surrogate). Furthermore, our results point that carbon-rich polysaccharides, such as transparent exopolymer particles, enhance heterotrophic N2 fixation, by forming microenvironments of intense metabolic activity, high carbon: nitrogen ratio, and possibly low O2 levels. The conclusions of this study indicate that diazotrophs in the eastern Mediterranean coast are primarily limited by organic carbon substrates, as possibly in many other marine regions.