Gram-negative bacteria were isolated from the rhizoplane of Brassica napus in France and from root nodules of Argyrolobium, uniflorum, Astragalus algerianus and Lathyrus numidicus growing in the infra-arid zone of southern Tunisia. Based on phylogenetic analysis of the 16S rRNA gene sequences, the seven isolates belong to the Alphaproteobacteria and are related to Phyllobacterium myrsinacearum strains. The isolates formed three clusters; clusters A and C consist of Tunisian strains, whereas cluster B consists of two strains from Brassica napus from France. Phylogenetic reconstruction based on the atpD gene strongly supports their affiliation to the genus Phyllobacterium. DNA-DNA hybridizations revealed that (i) none of the isolates belong to the species P. myrsinacearum, (ii) clusters A and C represent two distinct genomospecies and (iii) the two strains of cluster B represent two separate genomospecies. Distinctive phenotypic features were deduced from numerical analysis of phenotypic data. Based on this polyphasic approach, four novel species are proposed: Phyllobacterium leguminum sp. nov. (type strain ORS 1419(T) = CFBP 6745(T) = LMG 22833(T)), Phyllobacterium ifriqiyense sp. nov. (type strain STM 370(T) = CFBP 6742(T) = LMG 22831(T)), Phyllobacterium brassicacearum sp. nov. (type strain STM 196(T) = CFBP 5551(T) = LMG 22836(T)) and Phyllobacterium bourgognense sp. nov. (type strain STM 20(T) = CFBP 5553(T) =LMG 22837(T)). The description of the genus Phyllobacterium is emended accordingly