Background: Common bean (Phaseolus vulgaris L.) is the most important legume cropped worldwide for food production and its agronomic performance can be greatly improved if the benefits from symbiotic nitrogen fixation are maximized. The legume is known for its high promiscuity in nodulating with several Rhizobium species, but those belonging to the Rhizobium tropici "group" are the most successful and efficient in fixing nitrogen in tropical acid soils. Rhizobium leucaenae belongs to this group, which is abundant in the Brazilian "Cerrados" soils and frequently submitted to several environmental stresses. Here we present the first high-quality genome drafts of R. leucaenae, including the type strain CFN 299T and the very efficient strain CPAO 29.8. Our main objective was to identify features that explain the successful capacity of R. leucaenae in nodulating common bean under stressful environmental conditions. Results: The genomes of R. leucaenae strains CFN 299T and CPAO 29.8 were estimated at 6.7-6.8 Mbp; 7015 and 6899 coding sequences (CDS) were predicted, respectively, 6264 of which are common to both strains. The genomes of both strains present a large number of CDS that may confer tolerance of high temperatures, acid soils, salinity and water deficiency. Types I, II, IV-pili, IV and V secretion systems were present in both strains and might help soil and host colonization as well as the symbiotic performance under stressful conditions. The symbiotic plasmid of CPAO 29.8 is highly similar to already described tropici pSyms, including five copies of nodD and three of nodA genes. R. leucaenae CFN 299T is capable of synthesizing Nod factors in the absence of flavonoids when submitted to osmotic stress, indicating that under abiotic stress the regulation of nod genes might be different. Conclusion: A detailed study of the genes putatively related to stress tolerance in R. leucaenae highlighted an intricate pattern comprising a variety of mechanisms that are probably orchestrated to tolerate the stressful conditions to which the strains are submitted on a daily basis. The capacity to synthesize Nod factors under abiotic stress might follow the same regulatory pathways as in CIAT 899T and may help both to improve bacterial survival and to expand host range to guarantee the perpetuation of the symbiosis.