Improving post-wildfire restoration of foundational plant species is crucial for conserving imperiled ecosystems. We sought to better understand the initial establishment of sagebrush (Artemisia sp.), a foundational shrubland species over a vast area of western North America, in the first 1–2 years post-wildfire, a critical time period for population recovery. Field data from 460 sagebrush populations sampled across the Great Basin revealed several patterns. Sagebrush seedlings were uncommon in the first 1–2 years after fire, with none detected in 69% of plots, largely because most fires occurred in areas of low resistance to invasive species and resilience to disturbance (hereafter, R&R). Post-fire aerial seeding of sagebrush dramatically increased seedling occupancy, especially in low R&R areas, which exhibited a 3.4-fold increase in occupancy over similar unseeded locations. However, occupancy models and repeat surveys suggested exceptionally high mortality, as occupancy rates declined by as much as 50% between the first and second years after fire. We found the prevalence of “fertile island” microsites (patches beneath fire-consumed sagebrush) to be the best predictor of seedling occupancy, followed by aerial seeding status, native perennial grass cover, and years since fire. In populations where no sagebrush seeding occurred, seedlings were most likely to occur in locations with a combination of high fertile island microsite cover and close proximity to a remnant sagebrush plant. These important attributes were only present in 13% of post-fire locations, making them rare across the Great Basin. Finally, in the absence of fertile islands and remnant plants, seedling establishment was not observed in any unseeded areas, and rarely in seeded locations. Thus, local extirpation of sagebrush could have important, long-term implications for sagebrush reestablishment following future fires if there are no mature individuals to leave behind fertile islands or serve as remnant individuals. These findings highlight the importance of landscape legacy effects and could help guide where and how big sagebrush restoration is conducted in the future.