Genista saharae is an indigenous shrub legume that spontaneously grows in the northeastern Algerian Sahara. It is known for efficient dune fixation and soil preservation against desertification, due to its drought tolerance and its contribution to sustainable nitrogen resources implemented by biological N-2-fixation. In this study, the root nodule bacteria of G. saharae were investigated using phenotypic and phylogenetic characterization. A total of 57 rhizobial strains were isolated from nodules from several sites in the hyper-arid region of Metlili and Taibet (east Septentrional Sahara). They all nodulate G. saharae species but they differed in their symbiotic efficiency and effectiveness. The genetic diversity was assessed by sequencing three housekeeping genes (atpD, recA and 16S rRNA). The majority of isolates (81 %) belonged to the genus Ensifer (previously Sinorhizobium), represented mainly by the species Ensifer meliloti. The next most abundant genera were Neorhizobium (17 %) with 3 different species: N. alkalisoli, N. galegae and N. huautlense and Mesorhizobium (1.75 %) represented by the species M. camelthorni. Most of the isolated strains tolerated up to 4%(w/v) NaCl and grew at 45 degrees C. This study is the first report on the characterization of G. saharae microsymbionts in the Algerian Sahara.