Symbiosis between rhizobia and legumes is not only very important for the sustainable agriculture but also known as one of the model systems to study the mutualism between prokaryotes and eukaryotes. For a long time, studies on symbiotic nitrogen fixation of rhizobia have mainly focused on the role of key symbiosis genes involved in biosynthesis and regulation of Nod factors and nitrogenase. However, receiving these key genes does not guarantee rhizobia an effective symbiosis with legumes. Along with the rapid development and application of comparative and functional genomics, accumulated evidences indicate that rhizobia have recruited many lineage-specific dispensable genes to establish effective symbiosis with legumes, further revealing the complexity of mutualistic symbiosis. Here we review the cumulative evidence from recent genomics, genetics and experimental evolution studies to discuss the evolution of this complex symbiotic trait.