Common bean is one of the most important crops for human feed, and the most important legume for direct consumption by millions of people, especially in developing countries. It is a promiscuous host legume in terms of nodulation, able to associate with a broad and diverse range of rhizobia, although the competitiveness for nodulation and the nitrogen fixation capacity of most of these strains is generally low. As a result, common bean is very inefficient for symbiotic nitrogen fixation, and nitrogen has to be supplied with chemical fertilizers. In the last years, symbiotic nitrogen fixation has received increasing attention as a sustainable alternative to nitrogen fertilizers, and also as a more economic and available one in poor countries. Therefore, optimization of nitrogen fixation of bean-rhizobia symbioses and selection of efficient rhizobial strains should be a priority, which begins with the study of the natural diversity of the symbioses and the rhizobial populations associated. Natural rhizobia biodiversity that nodulates common bean may be a source of adaptive alleles acting through phenotypic plasticity. Crosses between accessions differing for nitrogen fixation may combine alleles that never meet in nature. Another way to discover adaptive genes is to use association genetics to identify loci that common bean plants use for enhanced biological nitrogen fixation and, in consequence, for marker assisted selection for genetic improvement of symbiotic nitrogen fixation. In this review, rhizobial biodiversity resources will be discussed, together with what is known about the loci that underlie such genetic variation, and the potential candidate genes that may influence the symbiosis’ fitness benefits, thus achieving an optimal nitrogen fixation capacity in order to help reduce reliance on nitrogen fertilizers in common bean.