Sagebrush landscapes provide habitat for Sage-Grouse and other sagebrush obligates, yet historical fire regimes and the structure of historical sagebrush landscapes are poorly known, hampering ecological restoration and management. To remedy this, General Land Office Survey (GLO) survey notes were used to reconstruct over two million hectares of historical vegetation for four sagebrush-dominated (Artemisia spp.) study areas in the western United States. Reconstructed vegetation was analyzed for fire indicators used to identify historical fires and reconstruct historical fire regimes. Historical fire-size distributions were inverse-J shaped, and one fire >100,000 ha was identified. Historical fire rotations were estimated at 171-342 years for Wyoming big sagebrush (A. tridentata ssp. wyomingensis) and 137-217 years for mountain big sagebrush (A. tridentata ssp. vaseyana). Historical fire and patch sizes were significantly larger in Wyoming big sagebrush than mountain big sagebrush, and historical fire rotations were significantly longer in Wyoming big sagebrush than mountain big sagebrush. Historical fire rotations in Wyoming were longer than those in other study areas. Fine-scale mosaics of burned and unburned area and larger unburned inclusions within fire perimeters were less common than in modern fires. Historical sagebrush landscapes were dominated by large, contiguous areas of sagebrush, though large grass-dominated areas and finer-scale mosaics of grass and sagebrush were also present in smaller amounts. Variation in sagebrush density was a common source of patchiness, and areas classified as 'dense' made up 24.5% of total sagebrush area, compared to 16.3% for 'scattered' sagebrush. Results suggest significant differences in historical and modern fire regimes. Modern fire rotations in Wyoming big sagebrush are shorter than historical fire rotations. Results also suggest that historical sagebrush landscapes would have fluctuated, because of infrequent episodes of large fires and long periods of recovery and maturity. Due to fragmentation of sagebrush landscapes, the large, contiguous expanses of sagebrush that dominated historically are most at risk and in need of conservation, including both dense and scattered sagebrush. Fire suppression in Wyoming big sagebrush may also be advisable, as modern fire rotations are shorter than their historical counterparts.