Naturally occurring soil rhizobia were isolated from the root nodules of cowpea and sesbania growing in the desert soils of the United Arab Emirates (UAE). Sequencing of the PCR amplified 16S rDNA identified the rhizobial isolates from cowpea as Sinorhizobium kostiense and S. terangae, and those from sesbania as S. meliloti, S. arboris and Sinorhizobium sp. nov. In vitro growth studies under a range of temperatures, salinities, pH and heavy metals revealed that the UAE strains have greater stress tolerance than the reference strain, Bradyrhizobium sp. strain TAL 169. A study of the nodulation ability of the two cowpea strains (S. kostiense and S. terangae) under saline conditions showed that  both the strains were effective in forming root nodules at high salinity (12 dS m^-1). To the authors’ knowledge, S. kostiense, S. terangae and S. arboris are reported for the first time from the Arabian Peninsula. Similarly, this study is the first to report symbiotic association of S. kostiense and S. terangae with cowpea and that of S. arboris with sesbania.  The tolerance to high levels of abiotic stresses makes these rhizobia highly valuable inoculums to improve the productivity of cowpea and sesbania cultivated in desert areas.