We compared 3 naturally ignited burns with unburned sites in the Grand Staircase-Escalante National Monument. Each burn site was restored with native and nonnative seed mixes, restored with native seeds only, or regenerated naturally. In general, burned sites had significantly lower native species richness (1.8 vs. 2.9 species), native species cover (11% vs. 22.5%), and soil crust cover (4.1% vs. 15%) than unburned sites. Most burned plots, seeded or not, had significantly higher average nonnative species richness and cover and lower average native species richness and cover than unburned sites. Regression tree analyses suggest site variation was equally important to rehabilitation results as seeding treatments. Low native species richness and cover, high soil C, and low cover of biological soil crusts may facilitate increased nonnative species richness and cover. Our study also found that unburned sites in the region had equally high cover of nonnative species compared with the rest of the Monument. Cheatgrass (Bromus tectorum) dominated both burned and unburned sites. Despite the invasion of cheatgrass, unburned sites still maintain higher native species richness; however, the high cover of cheatgrass may increase fire frequency, further reduce native species richness and cover, and ultimately change vegetation composition in juniper woodlands.