Streamflow is the component of the water cycle that is most accessible for human use. Tracking changes in the full range of streamflow regimes is crucial for a variety of practical purposes. However, a large proportion of basins in the world remain ungauged. Gravity Recovery and Climate Experiment (GRACE) provides information regarding terrestrial water storage anomalies (TWSA) all over the world, which may provide insights for streamflow in ungauged area. We propose storage-streamflow correlation spectrum (SSCS), which contains correlations between annual TWSA extrema and streamflow percentiles. We show that high correlations exist throughout the contiguous United States (CONUS), which can be exploited in the future to make predictions of inter-annual streamflow changes for ungauged basins, or hindcast TWSA using streamflow data. A wide variety of SSCS patterns emerge over CONUS but different climate may also produce similar SSCS patterns. These diverse patterns must be understood to estimate the uncertainty of making mutual predictions between storage and streamflow. To interpret the large volume of SSCS data, we classified all catchments in CONUS based on k-means clustering of SSCS. To further explore catchment characteristics that control SSCS, we trained a regression tree using climate and basin characteristics, which achieved some success. A few factors emerged as significant controls. Rigorous cross validation was conducted to select the most robust trees that explain why basins behave in a given way. Our work attempts to introduce a novel framework for analyzing relationships between terrestrial storage and streamflow in the full spectrum of flow regimes.