Greater sage-grouse (Centrocercus urophasianus) are threatened by a continued loss of sagebrush (Artemisia ssp.) habitat. Recent, large scale wildfires have elevated the risk to sage-grouse as it may take up to several decades to more than a century for naturally recovery of sage-grouse habitat (i.e. reestablishment of sagebrush). Sagebrush restoration after wildfires has had limited success and success varies considerably by method, site characteristics and interactions between them. However, almost no information is available to evaluate the potential success of different restoration methods across heterogeneous landscapes. Our objective was to compare different sagebrush restoration methods (broadcast seeding, broadcast seeding and packing, planting sagebrush seedlings, seed pillows, and natural recovery) across elevation gradients ranging from 1219 to > 2134 m (4000 to >7000 ft). We used 350 plots spread across approximately a million acres of sagebrush rangelands in Oregon that burned in two mega-fires in 2012. All sagebrush restoration methods were seeded in the fall of 2013, and then repeated on adjacent plots in 2014 with the exception of sagebrush seedlings; sagebrush seedlings were planted in the spring of 2014 and 2015. For Wyoming big sagebrush plots (elevation 4000 to 5000 ft), plots seeded in the fall on 2013 had on average < 0.01 sagebrush plants/m2 for all restoration methods. Plots seeded in the fall of 2014 had an average of 11.5 sagebrush plants/m2 (natural recovery plots had < 0.2 sagebrush plants/m2). Precipitation was on average 4% less than the 30 year average between September 2013 and August 2014; however, between September 2014 and May 2015 precipitation was on average 24% greater than the 30 year average. For mountain big sagebrush plots (elevation 5500 to 7000 ft), seeded plots were on average 4-fold greater than natural recovery plots (5.3 vs 1.2 plants/m2) for both seeded years. Perennial bunchgrass competition with sagebrush seedlings may have influenced sagebrush densities particularly in higher elevation plots; mountain big sagebrush plots had on average 7.8 bunchgrasses/m2, whereas Wyoming big sagebrush plot had on average 1.1 bunchgrasses/m2. Our research suggests that a hedge betting approach (employing more than one restoration method) can increase the probability of successful restoration. Broadcast seeding seed pillows and bare seed over two years resulted in a sagebrush restoration success rate of 86% compared to 36% if only one method was used in one year. Information generated from this study will help land managers successfully restore sage-grouse habitat after wildfires by pairing restoration methods with site characteristics.