We analyzed and radiocarbon-dated 205 fossil woodrat middens from 14 sites in central and northern Wyoming and adjacent Utah and Montana to document spatiotemporal patterns of Holocene invasion by Utah juniper (Juniperus osteosperma). Holocene migration into central and northern Wyoming and southern Montana from the south proceeded by a series of long-distance dispersal events, which were paced by climate variability and structured by the geographic distribution and connectivity of suitable habitats on the landscape. The migration of Utah juniper into the region involved multiple long-distance dispersal events, ranging from 30 to 135 km. One of the earliest established populations, on East Pryor Mountain in south central Montana, is currently the northernmost population of the species. Establishment by long-distance dispersal of that population and another in the Bighorn Basin occurred during a period of relatively dry climate between 7500 and 5400 years ago. Further expansion of these initial colonizing populations and backfilling to occupy suitable sites to the south was delayed during a wet period from 5400 to 2800 years ago. Development of dry conditions 2800 years ago led to a rapid expansion in which Utah juniper colonized sites throughout its current range. Landscape structure and climate variability play important roles in governing the pattern and pace of natural invasions and deserve close attention in studying and modeling plant invasions, whether exotic or natural.