Legume shrubs have great potential for rehabilitation of semi-arid degraded soils in Mediterranean ecosystems as they establish mutualistic symbiosis with N-fixing rhizobia. Eighty-eight symbiotic rhizobia were isolated from seven wild legume shrubs native of Sicily (Southern Italy) and grouped in operational taxonomic units (OTU) by analysis of the ribosomal internal transcribed spacer (ITS) polymorphism. Partial sequencing of 16S rRNA gene of representative isolates of each OTU revealed that most Genisteae symbionts are related to Bradyrhizobium canariense, B. japonicum and B. elkanii. Teline monspessulana was the only Genistea nodulated by Mesorhizobium strains, and Anagyris foetida (Thermopsideae) was promiscuosly nodulated by Rhizobium, Mesorhizobium, Agrobacterium and Bradyrhizobium strains. Analysis of the nodulation gene nodA assigned most Mediterranean Genisteae bradyrhizobia to clade II but also to clades IV, I and III, which included, so far, sequences of (sub)tropical and Australian isolates. The high diversity and low host specificity observed in most wild legumes isolates suggest that preferential associations may establish in the field depending on differences in the benefits conferred to the host and on competition ability. Once identified, these beneficial symbiosis can be exploited for rehabilitation of arid, low productive and human-impacted soils of the Mediterranean countries.