Himalayan rivers transport around a gigaton of sediment annually to ocean basins. Mountain valleys are an important component of this routing system: storage in these valleys acts to buffer climatic and tectonic signals recorded by downstream sedimentary systems. Despite a critical need to understand the spatial distribution, volume and longevity of these valley fills, controls on valley location and geometry are unknown, and estimates of sediment volumes are based on assumptions of valley-widening processes. Here we extract over 1.5 million valley-floor width measurements across the Himalaya to determine the dominant controls on valley-floor morphology and to assess sediment-storage processes. Using random forest regression, we show that channel steepness, a proxy for rock uplift, is a first-order control on valley-floor width. On the basis of a dataset of 1,148 exhumation rates, we find that valley-floor width decreases as exhumation rate increases. Our results suggest that valley-floor width is controlled by long-term tectonically driven exhumation rather than by water discharge or bedrock erodibility and that valley widening predominantly results from sediment deposition along low-gradient valley floors rather than lateral bedrock erosion.