Late Cenozoic stream incision and basin excavation have strongly influenced the modern Rocky Mountain landscape, but constraints on the timing and rates of erosion are limited. The geology of the Powder River basin provides an unusually good opportunity to address spatial and temporal patterns of stream incision. Numerous coal seams in the Paleocene Fort Union and Eocene Wasatch Formations within the basin have burned during late Cenozoic incision, as coal was exposed to dry and oxygen-rich near-surface conditions. The topography of this region is dominated by hills capped with clinker, sedimentary rocks metamorphosed by burning of underlying coal beds. We use (U-Th)/He ages of clinker to determine times of relatively rapid erosion, with the assumption that coal must be near Earth's surface to burn. Ages of 55 in situ samples range from 0.007 to 1.1 Ma. Clinker preferentially formed during times in which eccentricity of the Earth's orbit was high, times that typically but not always correlate with interglacial periods. Our data therefore suggest that rates of landscape evolution in this region are affected by climate fluctuations. Because the clinker ages correlate better with eccentricity time series than with an oxygen isotope record of global ice volume, we hypothesize that variations in solar insolation modulated by eccentricity have a larger impact on rates of landscape evolution in this region than do glacial-interglacial cycles.