Legumes form symbiotic relationship with root-nodule, rhizobia. The nitrogen (N2) fixed by legumes is a renewable source and of great importance to agriculture. Symbiotic nitrogen fixation (SNF) is constrained by multiple stresses and alleviating them would improve SNF contribution to agroecosystems. Genetic differences in adaptation tolerance to various stresses are known in both host plant and rhizobium. The discovery and use of promiscuous germplasm in soybean led to the release of high-yielding cultivars in Africa. High N2-fixing soybean cultivars are commercially grown in Australia and some countries in Africa and South America and those of pea in Russia. SNF is a complex trait, governed by multigenes with varying effects. Few major quantitative trait loci (QTL) and candidate genes underlying QTL are reported in grain and model legumes. Nodulating genes in model legumes are cloned and orthologs determined in grain legumes. Single nucleotide polymorphism (SNP) markers from nodulation genes are available in common bean and soybean. Genomes of chickpea, pigeonpea, and soybean; and genomes of several rhizobium species are decoded. Expression studies revealed few genes associated with SNF in model and grain legumes. Advances in host plant and rhizobium genomics are helping identify DNA markers to aid breeding of legume cultivars with high symbiotic efficiency. A paradigm shift is needed by breeding programs to simultaneously improve host plant and rhizobium to harness the strength of positive symbiotic interactions in cultivar development. Computation models based on metabolic reconstruction pathways are providing greater insights to explore genotype-phenotype relationships in SNF. Models to simulate the response of N2 fixation to a range of environmental variables and crop growth are assisting researchers to quantify SNF for efficient and sustainable agricultural production systems. Such knowledge helps identifying bottlenecks in specific legume-rhizobia systems that could be overcome by legume breeding to enhance SNF. This review discusses the recent developments to improve SNF and productivity of grain legumes.