Burkholderia has only recently been recognized as a potential nitrogen-fixing symbiont of legumes, but we find that the origins of symbiosis in Burkholderia are much deeper than previously suspected. We sampled 143 symbionts from 47 native species of Mimosa across 1800 km in central Brazil and found that 98% were Burkholderia. Gene sequences defined seven distinct and divergent species complexes within the genus Burkholderia. The symbiosis-related genes formed deep Burkholderia-specific clades, each specific to a species complex, implying that these genes diverged over a long period within Burkholderia without substantial horizontal gene transfer between species complexes.