A novel strain of Gram-negative, rod-shaped aerobic bacteria, identified as IY22, was isolated from the root nodules of Astragalus flavescens. The analysis of the 16S rDNA and recA (recombinase A) gene sequences indicated that the strain belongs to the genus Phyllobacterium. During the phylogenetic analysis, it was found that strain IY22 is closely related to P. trifolii strain PETP02T and P. bourgognense strain STM 201T. The genome of IY22 was determined to be 6,010,116 base pairs long with a DNA G+C ratio of 56.37 mol%. The average nucleotide identity (ANI) values showed a range from 91.7% to 93.6% when compared to its close relatives. Moreover, IY22 and related strains had digital DNA-DNA hybridization (dDDH) values ranging from 16.9% to 54.70%. Multiple genes (including nodACDSNZ, nifH/frxC, nifUS, fixABCJ, and sufABCDES) associated with symbiotic nitrogen fixation have been detected in strain IY22. Furthermore, this strain features genes that contribute to improving plant growth in various demanding environments. This study reports the first evidence of an association between A. flavescens and a rhizobial species. Native high-altitude legumes are a potential source of new rhizobia, and we believe that they act as a form of insurance for biodiversity against the threats of desertification and drought.