From noble beginnings as a prospective forage, polyploid Sorghum halepense (‘Johnsongrass’) is both an invasive species and one of the world’s worst agricultural weeds. Formed by S. bicolor x S. propinquum hybridization, we show S. halepense to have S. bicolor-enriched allele composition and striking mutations in 5,957 genes that differentiate it from representatives of its progenitor species and an outgroup. The spread of S. halepense may have been facilitated by introgression from closely-related cultivated sorghum near genetic loci affecting rhizome development, seed size, and levels of lutein, a photochemical protectant and abscisic acid precursor. Rhizomes, subterranean stems that store carbohydrates and spawn clonal propagules, have growth correlated with reproductive rather than other vegetative tissues, and increase survival of both temperate cold seasons and tropical dry seasons. Rhizomes of S. halepense are more extensive than those of its rhizomatous progenitor S. propinquum, with gene expression including many alleles from its non-rhizomatous S. bicolor progenitor. The first surviving polyploid in its lineage in approximately 96 million years, its post-Columbian spread across six continents carried rich genetic diversity that in the United States has facilitated transition from agricultural to non-agricultural niches. Projected to spread another 200-600 km northward in the coming century, despite its drawbacks S. halepense may offer novel alleles and traits of value to improvement of sorghum.