Rhizosphere bacteria were isolated from Costularia spp., pioneer sedges from ultramafic soils in New Caledonia, which is a hotspot of biodiversity in the South Pacific. Genus identification, ability to tolerate edaphic constraints, and plant-growth-promoting (PGP) properties were analysed. We found that 10(5) colony-forming units per gram of root were dominated by Proteobacteria (69%) and comprised 21 genera, including Burkholderia (28%), Curtobacterium (15%), Bradyrhizobium (9%), Sphingomonas (8%), Rhizobium (7%), and Bacillus (5%). High proportions of bacteria tolerated many elements of the extreme edaphic conditions: 82% tolerated 100 μmol·L(-1) chromium, 70% 1 mmol·L(-1) nickel, 63% 10 mmol·L(-1) manganese, 24% 1 mmol·L(-1) cobalt, and 42% an unbalanced calcium/magnesium ratio (1/16). These strains also exhibited multiple PGP properties, including the ability to produce ammonia (65%), indole-3-acetic acid (60%), siderophores (52%), and 1-aminocyclopropane-1-carboxylate (ACC) deaminase (39%); as well as the capacity to solubilize phosphates (19%). The best-performing strains were inoculated with Sorghum sp. grown on ultramafic substrate. Three strains significantly enhanced the shoot biomass by up to 33%. The most successful strains influenced plant nutrition through the mobilization of metals in roots and a reduction of metal transfer to shoots. These results suggest a key role of these bacteria in plant growth, nutrition, and adaptation to the ultramafic constraints.