Legume nodules, specialized structures for nitrogen fixation, are probably the result of coevolution of plants and ancestral rhizobia. Among the evolutionary processes leading to legume radiation and divergence, coevolution with rhizobia might have occurred. Alternatively, bacteria could have been constantly selected by plants, with bacteria slightly influencing plant evolution (required to fulfill the criteria for a coevolutionary hypothesis). Evidence of bacterial effects on plant evolution is scarce but being searched for. Bacterial genetic plasticity may be indicative of the large capacity of Rhizobium to adapt to legumes. Events such as symbiotic replacement, easy recruitment of symbiotic bacteria by legume plants, and lateral transfer of symbiotic genes seem to erase the coevolutionary or selected relationships in rhizobial-legume symbiosis. In particular, the hypotheses proposed are (1) Rhizobium replaced Bradyrhizobium in a few hosts of the Phaseoleae tribe, Phaseolus vulgaris and P. coccineus; (2) Rhizobium etli as a species did not coevolve with bean; and (3) beta-Proteobacteria replaced alpha-Proteobacteria in South American mimosas. Novel results on symbiosis suggest a more complex evolutionary process for nodulation that may include multiple organisms, such as mycorrhiza, nematodes, and other bacteria in addition to rhizobia.