Cowpea (Vigna unguiculata) and peanut (Arachis hypogaea) in southern Africa are nodulated by a genetically diverse group of Bradyrhizobium strains. To determine the identity of these bacteria, a collection of 22 isolates originating from the root nodules of both hosts in Botswana and South Africa was investigated using the combined sequences for the core genome genes rrs, recA, and glnII. These data separated the majority of the isolates into one of three unique lineages that most likely represent novel Bradyrhizobium species. Some isolates were also conspecific with B. yuanmingense and with B. elkanii, although none grouped with B. japonicum, B. canariense or B. liaoningense. To study the evolution of nodulation genes in these bacteria, the common nodulation gene, nodA, and host-specific nodulation genes, nodZ, noeE, and noeI, were analyzed. The nodA phylogeny showed that the cowpea and peanut Bradyrhizobium isolates represent various locally adapted groups or ecotypes that form part of Clade III of the seven known BradyrhizobiumnodA clades. This large and highly diverse clade comprises all strains from sub-Saharan Africa, as well as some originating from the Americas, Australia, Indonesia, China and Japan. Some similar groupings were supported by the other nodulation genes, although the overall phylogenies for the nodulation genes were incongruent with that inferred from the core genome genes, suggesting that horizontal gene transfer significantly influences the evolution of cowpea and peanut root-nodule bacteria. Furthermore, identification of the nodZ, noeI, and noeE genes in the isolates tested indicates that African Bradyrhizobium species may produce highly decorated nodulation factors, which potentially represent an important adaptation enabling nodulation of a great variety of legumes inhabiting the African continent.