Members of the genus Burkholderia (β-proteobacteria) have only recently been shown to be able to establish a nitrogen-fixing symbiosis with several legumes, which is why they are also referred to as β-rhizobia. Therefore, very little is known about the competitiveness of these species to nodulate different legume host plants. In this study, we tested the competitiveness of several Burkholderia type strains (B. diazotrophica, B. mimosarum, B. phymatum, B. sabiae, B. symbiotica and B. tuberum) to nodulate four legumes (Phaseolus vulgaris, Macroptilium atropurpureum, Vigna unguiculata and Mimosa pudica) under our closely defined growth conditions. The assessment of nodule occupancy of these species on different legume host plants revealed that B. phymatum was the most competitive strain in the three papilionoid legumes (bean, cowpea and siratro), while B. mimosarum outcompeted the other strains in mimosa. The analysis of phenotypes known to play a role in nodulation competitiveness (motility, exopolysaccharide production) and additional in vitro competition assays among β-rhizobial strains suggested that B. phymatum has the potential to be a very competitive legume symbiont.