Although Medicago sativa forms highly effective symbioses with the comparatively acid-sensitive genus Ensifer, its introduction into acid soils appears to have selected for symbiotic interactions with acid-tolerant R. favelukesii strains. Rhizobium favelukesii has the unusual ability of being able to nodulate and fix nitrogen, albeit sub-optimally, not only with M. sativa but also with the promiscuous host Phaseolus vulgaris. Here we describe the genome of R. favelukesii OR191 and genomic features important for the symbiotic interaction with both of these hosts. The OR191 draft genome contained acid adaptation loci, including the highly acid-inducible lpiA/acvB operon and olsC, required for production of lysine- and ornithine-containing membrane lipids, respectively. The olsC gene was also present in other acid-tolerant Rhizobium strains but absent from the more acid-sensitive Ensifer microsymbionts. The OR191 symbiotic genes were in general more closely related to those found in Medicago microsymbionts. OR191 contained the nodA, nodEF, nodHPQ, and nodL genes for synthesis of polyunsaturated, sulfated and acetylated Nod factors that are important for symbiosis with Medicago, but contained a truncated nodG, which may decrease nodulation efficiency with M. sativa. OR191 contained an E. meliloti type BacA, which has been shown to specifically protect Ensifer microsymbionts from Medicago nodule-specific cysteine-rich peptides. The nitrogen fixation genes nifQWZS were present in OR191 and P. vulgaris microsymbionts but absent from E. meliloti-Medicago microsymbionts. The ability of OR191 to nodulate and fix nitrogen symbiotically with P. vulgaris indicates that this host has less stringent requirements for nodulation than M. sativa but may need rhizobial strains that possess nifQWZS for N2-fixation to occur. OR191 possessed the exo genes required for the biosynthesis of succinoglycan, which is required for the Ensifer-Medicago symbiosis. However, 1H-NMR spectra revealed that, in the conditions tested, OR191 exopolysaccharide did not contain a succinyl substituent but instead contained a 3-hydroxybutyrate moiety, which may affect its symbiotic performance with Medicago hosts. These findings provide a foundation for the genetic basis of nodulation requirements and symbiotic effectiveness with different hosts.