The width of fluvial valley-floors is a key parameter to quantifying the morphology of mountain regions. Valley-floor width is relevant to diverse fields including sedimentology, fluvial geomorphology, and archaeology. The width of valleys has been argued to depend on climatic and tectonic conditions, on the hydraulics and hydrology of the river channel that forms the valley, and on sediment supply from valley walls. Yet, so far, a physically-based model that can be used to predict valley width is lacking. Here, we derive such a model and test it against three different datasets. The model applies to valleys that are carved by a river migrating across the valley floor, and includes the effects of uplift and lateral hillslope sediment supply. Valley width is controlled mainly by the mobility-uplift number, which is the ratio between lateral channel mobility and uplift rate. At high values of the mobility-uplift number, the valley evolves to the channel-belt width, which is the width of the area actively reworked by the river in an unconfined setting. At low values of the mobility-uplift number, valley width corresponds to channel width. Between these limits, valley width is linked to the mobility-uplift number by a logarithmic function. We compare the model to independent data sets of valleys in experimental and natural uplifting landscapes and show that it closely predicts the first-order relationship between valley width and the mobility-uplift number.