Eukaryotes often form symbioses with microorganisms. Among these, associations between plants and nitrogen-fixing bacteria are responsible for the nitrogen input into various ecological niches. Plants of many different families have evolved the capacity to develop root or stem nodules with diverse genera of soil bacteria. Of these, symbioses between legumes and rhizobia (Azorhizobium, Bradyrhizobium, Mesorhizobium, and Rhizobium) are the most important from an agricultural perspective. Nitrogen-fixing nodules arise when symbiotic rhizobia penetrate their hosts in a strictly controlled and coordinated manner. Molecular codes are exchanged between the symbionts in the rhizosphere to select compatible rhizobia from pathogens. Entry into the plant is restricted to bacteria that have the "keys" to a succession of legume "doors". Some symbionts intimately associate with many different partners (and are thus promiscuous), while others are more selective and have a narrow host range. For historical reasons, narrow host range has been more intensively investigated than promiscuity. In our view, this has given a false impression of specificity in legume-Rhizobium associations. Rather, we suggest that restricted host ranges are limited to specific niches and represent specialization of widespread and more ancestral promiscuous symbioses. Here we analyze the molecular mechanisms governing symbiotic promiscuity in rhizobia and show that it is controlled by a number of molecular keys.