Polyphasic characterization of 61 bacteria isolated from root nodules of Medicago arborea (Medic tree) plants growing in 4 arid soils of the arid eastern area of Morocco was studied. All the isolates characterized were fast growers. The phenotypic, symbiotic, and cultural characteristics analyzed allowed the description of a broad physiological diversity among the isolates. The results obtained suggest that the phenotype of these rhizobia might have evolved to adapt to the local conditions. The genetic characterization consisted of an analysis of the rep-PCR (repetitive extragenic palindromic polymerase chain reaction) fingerprints and a PCR-based RFLP (restriction fragment length polymorphism) of the 16S rDNA patterns. The diversity of the isolates was investigated by rep-PCR, giving a similarity of 62%, delineated into 3 clusters, 4 groups, and 6 subclusters. This wide diversity was also observed by a phenotypic approach, where the carbohydrate assimilation test was the most discriminating. The results show a relationship between rep-PCR fingerprinting and sugar assimilation, which are complementary in diversity investigation. The nearly complete 16S rRNA gene sequence from representative strains of each soil showed they are closely related to members of the genus Ensifer of the family Rhizobiaceae within the Alphaproteobacteria and shows the highest similitude values (99.93%/100%) with Ensifer meliloti LMG 6133(T) (X67222). Sequencing of the symbiotic nodC gene from 7 representative strains revealed they had 94.89% identity with the nodC sequence of the type strain E. meliloti LMG 6133(T) (EF428922). Therefore, the 61 M. arborea isolates from the 4 different soils have the same phylogenetic affiliation, which proves the restricted host specificity among M. arborea species.