Although invasions by exotic plants have increased dramatically as human travel and commerce have increased, few have been comprehensively described. Understanding the patterns of invasive species’ spread over space and time will help guide management activities and policy. Tracing the earliest appearances of an exotic plant reveals likely sites of introduction, paving the way for genetic studies to quantify founder events and identify potential source populations. Red brome (Bromus madritensis subsp. rubens) is a Mediterranean winter annual grass that has invaded even relatively undisturbed areas of western North America, where it threatens native plant communities. This study used herbarium records and contemporary published accounts to trace the early introductions and subsequent spread of red brome in western North America. The results challenge the most frequently cited sources describing the early history of this grass and suggest three possible modes for early introductions: the California Gold Rush and Central Valley wheat, southern California shipping, and northern California sheep. Subsequent periods of most rapid spread into new areas, from 1930 to 1942, and of greatest spread into new regions, during the past 50 years, coincide with ‘warm’ Pacific Decadal Oscillation regimes, which are linked to increased winter precipitation in the southwestern USA and northern Mexico. Global environmental change, including increased atmospheric CO₂ levels and N deposition, may be contributing to the success of red brome, relative to native species.