Local adaptation may facilitate range expansion during invasions, but the mechanisms promoting destructive invasions remain unclear. Cheatgrass (Bromus tectorum), native to Eurasia and Africa, has invaded globally, with particularly severe impacts in western North America. We sequenced 307 genotypes and conducted controlled experiments. We found that diverse lineages invaded North America, where long-distance gene flow is common. Ancestry and phenotypic clines in the native range predicted those in the invaded range, indicating pre-adapted genotypes colonized different regions. Common gardens showed directional selection on flowering time that reversed between warm and cold sites, potentially maintaining clines. In the Great Basin, genomic predictions of strong local adaptation identified sites where cheatgrass is most dominant. Preventing new introductions that may fuel adaptation is critical for managing ongoing invasions.