We isolated three slow-growing rhizobial strains (1.29L, 1.27L, and 5.13L) from root nodules of Acacia saligna collected at two contaminated sites in Tunisia and characterized them using a polyphasic taxonomic approach. Phylogenetic, MLSA, and comparative genomic analyses placed the isolates within the Bradyrhizobium japonicum supergroup but clearly distinct from described species, with 1.29Lᵀ as the proposed type strain. The strains showed heavy-metal tolerance and plant growth–promoting traits (IAA production, phosphate solubilization, siderophores), supporting the proposal of a new species, Bradyrhizobium cedriense sp. nov.