Himalayan rivers transport ≈ 103 Mt of sediment annually to ocean basins. River valleys are an important component of this routing system: while sediment is stored in valleys, signals of climate change and erosional patterns can be modified or even destroyed. 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 never-tested assumptions of valley widening processes. Here we extract 1,644,215 valley-floor width measurements across the Himalaya to determine the dominant controls on valley-floor morphology for the first time, and to test underlying assumptions of sediment storage volumes. We use random forest regression to estimate the importance of potential controlling variables, and find that channel steepness, a proxy for rock uplift, is a first-order control on valley-floor width. We also analyse a novel dataset of 1,797 exhumation rates and find that valley-floor width decreases as exhumation rate increases. We therefore suggest that valley-floor width is adjusted to long-term tectonic exhumation rather than being controlled 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.