Leifsonia xyli subsp. xyli, causal agent of ratoon stunting disease (RSD) of sugarcane (Saccharum interspecific hybrids), is the most well-known member of the Microbacteriaceae genus Leifsonia. However, the presence of other Leifsonia strains associated with sugarcane has not been reported. A total of 697 Australian and 40 Indonesian sugarcane fields were screened by leaf sheath biopsy (LSB) PCR using primers specific for L. xyli subsp. xyli, in addition to primers designed to amplify DNA from other members of the genus Leifsonia. While L. xyli subsp. xyli was detected in 126 fields, a total of 37 distinct and novel Leifsonia and non-Leifsonia strains were detected in 116 fields. Representatives of these strains were also detected in multiple samples of expressed xylem sap. Sequencing and phylogenetic analyses demonstrated the presence of a broad complex of novel Leifsonia strains, in addition to strains closely related to the recently erected Cnuibacter genus. Attempts to isolate Leifsonia strains were unsuccessful; however, one strain related to Cnuibacter was recovered from expressed xylem sap. Among the genetically diverse lineages discovered, identical genotypes were present in multiple sugarcane varieties growing in disparate regions in different years, strongly suggesting an ongoing association with sugarcane. The epidemiological significance of these strains is unknown, but there is evidence that they can interfere with serological and microscopic RSD diagnostics, and there is the potential that they may represent new and distinct pathologies of sugarcane.