The South African invasive legume Dipogon lignosus (Phaseoleae) produces nodules with both determinate and indeterminate characteristics in New Zealand (NZ) soils. Ten bacterial isolates produced functional nodules on D. lignosus. The 16S ribosomal RNA (rRNA) gene sequences identified one isolate as Bradyrhizobium sp., one isolate as Rhizobium sp. and eight isolates as Burkholderia sp. The Bradyrhizobium sp. and Rhizobium sp. 16S rRNA sequences were identical to those of strains previously isolated from crop plants and may have originated from inocula used on crops. Both 16S rRNA and DNA recombinase A (recA) gene sequences placed the eight Burkholderia isolates separate from previously described Burkholderia rhizobial species. However, the isolates showed a very close relationship to Burkholderia rhizobial strains isolated from South African plants with respect to their nitrogenase iron protein (nifH), N-acyltransferase nodulation protein A (nodA) and N-acetylglucosaminyl transferase nodulation protein C (nodC) gene sequences. Gene sequences and enterobacterial repetitive intergenic consensus (ERIC) PCR and repetitive element palindromic PCR (rep-PCR) banding patterns indicated that the eight Burkholderia isolates separated into five clones of one strain and three of another. One strain was tested and shown to produce functional nodules on a range of South African plants previously reported to be nodulated by Burkholderia tuberum STM678(T) which was isolated from the Cape Region. Thus, evidence is strong that the Burkholderia strains isolated here originated in South Africa and were somehow transported with the plants from their native habitat to NZ. It is possible that the strains are of a new species capable of nodulating legumes.