The changing hydrologic regime of the Upper Colorado River Basin presents a daunting challenge for water resources management. A major source of concern is that of ascertaining the nature of runoff variability and re-calibrating the systemic management and planning based on a more reliable envelope of water supply variations to meet societal needs. In this letter, we examine the long-term variability and change in the Upper Colorado annual runoff volume—quantified as shifts in the mean, interannual variability, and persistence—in a recent tree-ring based reconstruction extending back to 762AD. A simple model for reservoir storage requirement shows sensitivity to the changing hydrologic regime, with episodes of abrupt shifts toward significantly higher storage requirements, often not readily evident in runoff statistics. The results also suggest that benchmarking of climate models for regional water resources assessment should focus on the runoff statistics that are most relevant for storage requirement computations.