It is hotly debated whether and how climate changes are recorded by terrestrial stratigraphy. Basin sediments produced by catchment-alluvial fan systems may record past climate over a variety of timescales, and could offer unique information about how climate controls sedimentation. Unfortunately, there are fundamental uncertainties about how climatic variables such as rainfall and temperature translate into sedimentological signals. Here, we examine 35 debris flow fan surfaces in Owens Valley, California, that record deposition throughout the past 125,000 years, during which climate has varied significantly. We show that the last full glacial-interglacial cycle is recorded with high fidelity by the grain size distributions of the debris flow deposits. These flows transported finer sediment during the cooler glacial climate, and became systematically coarser-grained as the climate warmed and dried. We explore the physical mechanisms that might explain this signal, and rule out changes in sediment supply through time. Instead, we propose that grain size records past changes in storm intensity, which is responsible for debris flow initiation in this area and is decoupled from average rainfall rates. This is supported by an exponential Clausius-Clapeyron-style scaling between grain size and temperature, and also reconciles with climate dynamics, and the initiation of debris flows, and observations from El Niño events. The fact that these alluvial fans exhibit a strong, sustained sensitivity to orbital climate changes sheds new light on how eroding landscapes and their sedimentary products respond to climatic forcing. Finally, our findings highlight the importance of threshold-controlled events, such as storms and debris flows, in driving erosion and sedimentation at the Earth's surface in response to climate change.