The Arctic is warming at an unprecedented rate. One relatively under researched process is how seasonally frozen soils and changes thereof affect the water cycle. As frozen soils thaw, flow pathways within a watershed open, allowing for enhanced hydrologic connectivity between groundwater and rivers. As the connectivity of flow paths increase, the storage-discharge relationship of a watershed changes. The objective of this study is to quantify trends and spatio-temporal differences in the degree of linearity in the storage-discharge relationships for sixteen watersheds within Northern Sweden throughout the years of 1950 and 2018. We demonstrate a clear increase in non-linearity of the storage-discharge relationship over time for all catchments with twelve out of sixteen watersheds (75%) having a statistically significant increase in non-linearity. Springs have significantly more linear storage-discharge relationships than summer for twelve watersheds (75%), which supports the idea that seasonally frozen soil with a low degree of hydrological connectivity have a linear storage-discharge relationship. For the period considered, spring showed the greater change in storage-discharge relationship trends than summer, signifying changes in recessions are occurring during the thawing period. Separate storage-discharge analyses combined with preceding winter conditions demonstrated that especially cold winters with little snow yield springs and summers with more linear storage-discharge relationships. We show that streamflow recession analysis shows ongoing hydrological change of an arctic landscape as well as offers new metrics for tracking the change across arctic and sub-arctic landscapes.