Leaf scald caused by Xanthomonas albilineans (Xa) is a major bacterial disease in sugarcane that represents a threat to the global sugar industry. Little is known about the population structure and genetic evolution of this pathogen. In this study, 39 Xa strains were collected from 6 provinces in China. Of these strains, 15 and 24 were isolated from Saccharum spp. hybrid and S. officinarum plants, respectively. Based on multilocus sequence analysis (MLSA), with five housekeeping genes, these strains were clustered into two distinct phylogenetic groups (I and II). Group I included 26 strains from 2 host plants, Saccharum spp. hybrid and S. officinarum collected from 6 provinces, while Group II consisted of 13 strains from S. officinarum plants in the Zhejiang province. Among the 39 Xa strains, nucleotide sequence identities from 5 housekeeping genes were: ABC (99.6–100%), gyrB (99.3–100%), rpoD (98.4–100%), atpD (97.0–100%), and glnA (97.6–100%). These strains were clustered into six groups (A–F), based on the rep-PCR fingerprinting, using primers for ERIC2, BOX A1R, and (GTG)5. UPGMA and PCoA analyses revealed that group A had the most strains (24), followed by group C with 11 strains, while there was 1 strain each in groups B and D–F. Neutral tests showed that the Xa population in S. officinarum had a trend toward population expansion. Selection pressure analysis showed purification selection on five concatenated housekeeping genes from all tested strains. Significant genetic differentiation and infrequent gene flow were found between two Xa populations hosted in Saccharum spp. hybrids and S. officinarum. Altogether, these results provide evidence of obvious genetic divergence and population structures among Xa strains from China.