A variety of watershed responses to climate change are expected due to non-linear interactions between various hydrologic processes acting at different timescales that are modulated by watershed properties. Changes in statistical structure (spectral properties) of streamflow in the USA due to climate change were studied for water years 1980-2013. The Fractionally differenced Autoregressive Integrated Moving Average (FARIMA) model was fit to the deseasonalized streamflow time-series to model its statistical structure. FARIMA allows the separation of streamflow into low frequency (slowly varying) and high frequency (fast varying) components. Results show that in snow dominated watersheds, the contribution of low frequency components to total streamflow variance has decreased over the study period, and the contribution of high frequency components has increased. The change in snow dominated watersheds was primarily driven by changes in rainfall statistics and changes in snow water equivalent but also by changes in seasonal temperature statistics. Among rain-driven watersheds, the contribution of high frequency components generally increased in arid regions but decreased in humid regions. In both humid and arid rain-driven watersheds, increasing winter temperature was responsible for the change in streamflow regimes. These results have consequences for predictability of streamflow in the presence of climate change. We expect that changes in the high frequency component will result in poorer predictability of streamflow.