Acacia saligna is an invasive alien species that has the ability to establish symbiotic relationships with rhizobia. In the present study, genotypic and symbiotic diversity of native rhizobia associated with A. saligna in Tunisia were studied. A total of 100 bacterial strains were selected and three different ribotypes were identified based on rrs PCR-RFLP analysis. Sequence analyses of rrs and four housekeeping genes (recA, atpD, gyrB and glnII) assigned 30 isolates to four putative new lineages and a single strain to Sinorhizobium meliloti. Thirteen slow-growing isolates representing the most dominant IGS (intergenic spacer) profile clustered distinctly from known rhizobia species within Bradyrhizobium with the closest related species being Bradyrhizobium shewense and Bradyrhizobium niftali, which had 95.17% and 95.1% sequence identity, respectively. Two slow-growing isolates, 1AS28L and 5AS6L, had B. frederekii as their closest species with a sequence identity of 95.2%, an indication that these strains could constitute a new lineage. Strains 1AS14I, 1AS12I and 6AS6 clustered distinctly from known rhizobia species but within the Rhizobium leguminosarum complex (Rlc) with the most closely related species being Rhizobium indicum with 96.3% sequence identity. Similarly, the remaining 11 strains showed 96.9 % and 97.2% similarity values with R. changzhiense and R. indicum, respectively. Based on nodC and nodA phylogenies and cross inoculation tests, these 14 strains of Rlc species clearly diverged from strains of Sinorhizobium and Rlc symbiovars, and formed a new symbiovar for which the name sv. “salignae” is proposed. Bacterial strains isolated in this study that were taxonomically assigned to Bradyrhizobium harbored different symbiotic genes and the data suggested a new symbiovar, for which sv. “cyanophyllae” is proposed. Isolates formed effective nodules on A. saligna.