Study region: The Colorado River Basin (CRB), a semi-arid watershed in the southwestern U.S., supplies water to more than 40 million people and is one of the most climate-vulnerable regions in North America. Study focus: Hypsometric (area-elevation) analysis is used to infer water storage change. However, DEMs from the Shuttle Radar Topography Mission (SRTM), acquired in 2000, cannot capture elevation beneath water surfaces. Thus, areas exposed by post-2000 water losses lack reliable elevation data, hindering storage-loss estimates. To address this limitation, we introduced Global Ecosystem Dynamics Investigation (GEDI) to estimate storage loss and SRTM to derive storage gain, coupled with Global Surface Water (GSW). We quantify water storage changes for 20 lakes/reservoirs (>10 km & sup2;; 2000-2021). New hydrological insights for the region: Results indicate a substantial decrease in surface water area (similar to 551 km & sup2;) and a net loss of similar to 24 km & sup3; of water storage (233 days of the U.S. water use), with remarkable reductions in Lake Mead and Lake Powell. Validation against in-situ observations shows average accuracy of similar to 75.9%, supporting the reliability of GEDI-based estimates for monitoring storage loss. Trend analysis suggests that rising land surface temperature, increasing actual evapotranspiration, and insufficient precipitation are hydroclimatic stressors that amplify depletion. Our analytic workflow is well-suited in regions with limited in-situ observations, offering a scalable, cost-effective framework for monitoring water storage dynamics.