The Arctic is warming at an unprecedented rate. We hypothesis that as seasonally frozen soils thaw and recede in extent as a response to this warming, flow path diversity and thus hydrologic connectivity increases. This enhanced hydrologic connectivity then increases the non-linearity of the storage-discharge relationship in a catchment. The objective of this study is to test this hypothesis by quantifying trends and spatio-temporal differences in the degree of linearity in the storage-discharge relationships for 16 catchments within Northern Sweden from 1950 to 2018. We demonstrate a clear increase in non-linearity of the storage-discharge relationship over time for all catchments with 75% showing a statistically significant increase in non-linearity. Spring has significantly more linear storage-discharge relationships than summer for most catchments (75%) supporting the idea that seasonally frozen soils with a low degree of hydrological connectivity have a linear storage-discharge relationship. For the period considered, spring also showed greater change in storage-discharge relationship trends than summer signifying that changes in recessions are primarily occurring during the thawing period. Separate storage-discharge analyses combined with preceding winter conditions demonstrated that especially cold winters with little snow yielded springs and summers with more linear storage-discharge relationships. We show that streamflow recession analysis reflects ongoing hydrological change of an arctic landscape as well as offering new metrics for tracking change across arctic and sub-arctic landscapes.