Unraveling the effects of climate and land-use on historical fire regimes provides important insights into broader human-fire-climate dynamics, which are necessary for ecologically-based forest management. We developed a spatial human land-use model for Navajo Nation forests across which we sampled a network of tree-ring fire history sites to reflect contrasting historical land-use intensity: high human use, primarily in the Chuska Mountains, and low human use, primarily on the central Defiance Plateau. We tested for and compared human- and climate-driven changes in the fire regimes by applying change point detection, regression, and superposed epoch analyses. The historical fire regimes and fire-climate relationships reflect those of similar forests regionally, and are similar between the two Navajo landscapes until the early 1800s. We then determined that a previously identified, localized, early (1830s) decline in fire activity was geographically widespread across higher human use sites. In contrast, fires continued to burn uninterrupted through this period at the lower use sites. Though the 1830s included significantly wet and cold periods that could have contributed to fire regime decline, human factors pose a more spatio-temporally consistent explanation. A rise in Navajo pastoralism in the 1820s-1830s was concentrated seasonally in the heavy use sites. By the 1880s, livestock numbers more than doubled, grazing became far more spatially widespread, and frequent fire regimes of Navajo forests collapsed. The last widespread fire recorded on either landscape was in 1886. In the Chuska Mountains, livestock and fire co-existed for over 50 years between the initial 1832 fire decline and the end of frequent fires after 1886, an exceptional pattern in the western US. Though unique in its timing, character, and spatial dynamics, the collapse of historical fire regimes in Navajo forests contributed to now over a century without frequent surface fire, leaving Navajo forests at risk for large, uncharacteristic high-severity fires.