Feeding the growing global population, anticipated to be 8 billion by the year 2020, is one of the most important recent challenges of agriculture. The increase in cereal grain yield, to cope with this demand, directly implies a dramatic increase in the use of nitrogen-based fertilizers and agrochemicals. Some of these intensive agricultural practices have progressive detrimental effects on the environment. This review is focused on some novel insights gained into the understanding of associative and symbiotic interactions of plants with nitrogen-fixing organisms that makes Biological Nitrogen Fixation (BNF) a viable answer to this compelling dilemma.