Aims: To survey the occurrence of nodulated legumes in the arid and semi-arid areas of Western Rajasthan and to characterize their associated symbiotic bacteria. Methods: Herbaceous annual species were excavated whole, while tree species were studied as seedlings in the field or as trap plants in pot experiments. Nodules were examined by microscopy to confirm their effectiveness and to determine their internal structure. Bacteria isolated from the nodules were authenticated on their original hosts and were identified on the basis of 16S rRNA sequencing. Phylogenetic trees were inferred using the neighbour-joining method. Results: We studied 35 of more than 50 species of native legume reported from these areas. Legumes are drought escaping (annual species), drought tolerant perennials or trees possessing deep root systems and other adaptations to arid conditions. Nodulation was recorded in all members of the Papilionoideae and Mimosoideae, but only one species of Caesalpinioideae. Internal structure of nodules varied within these groups, especially with respect to the presence or absence of uninfected cells in the infected region. Full 16S rRNA gene sequencing revealed that the nodules harboured a range of nodulating bacteria belonging to the genera Sinorhizobium, Rhizobium and Bradyrhizobium, within which they formed separate sub clades. Conclusions: This study extends the range of legumes known to grow and nodulate in semi-arid regions, and provides information about their endosymbionts.