Acacia spirorbis subsp. spirorbis Labill. is a widespread tree legume endemic to New Caledonia that grows in ultramafic (UF) and volcano-sedimentary (VS) soils. The aim of this study was to assess the symbiotic promiscuity of A. spirorbis with nodulating and nitrogen-fixing rhizobia in harsh edaphic conditions. Forty bacterial strains were isolated from root nodules and characterized through (i) multilocus sequence analyses, (ii) symbiotic efficiency and (iii) tolerance to metals. Notably, 32.5% of the rhizobia belonged to the Paraburkholderia genus and were only found in UF soils. The remaining 67.5%, isolated from both UF and VS soils, belonged to the Bradyrhizobium genus. Strains of the Paraburkholderia genus showed significantly higher nitrogen-fixing capacities than those of Bradyrhizobium genus. Strains of the two genera isolated from UF soils showed high metal tolerance and the respective genes occurred in 50% of strains. This is the first report of both alpha- and beta-rhizobia strains associated to an Acacia species adapted to UF and VS soils. Our findings suggest that A. spirorbis is an adaptive plant that establishes symbioses with whatever rhizobia is present in the soil, thus enabling the colonization of contrasted ecosystems.