Exploration of SST-Streamflow connection unravels the large scale climate influences that have a potential role in modulating local hydrological components. Most studies exploring this relationship only focus on seasonal or annual scales however, various atmospheric and oceanic phenomena occur at different timescales, which need to be considered. This study investigates the influence of sea surface temperature (SST) on German streamflow, divided into Alpine, Atlantic and Continental streamflow regions, at timescales ranging from sub-seasonal to decadal by integrating wavelet transform and complex network techniques. Wavelet transform is used to decompose the time series into multiple frequency signals, and the spatial connections are identified based on these decomposed signals for the 99 percentile correlation coefficient value by applying network theory. The degree centrality metric is used to evaluate the characteristics of the spatially embedded networks. Our results re-establish known SST regions that have a potential connection with the various streamflow regions of Germany. Spatial patterns that resemble the North Atlantic SST tripole-like pattern is predominant for Alpine streamflow regions at lower timescale. Equatorial Atlantic Mode regions observed for Atlantic streamflow at inter-annual timescale and Vb weather system connected regions in the Mediterranean Sea have appeared for all the streamflow regions of Germany. Besides, continental streamflow regions exhibited combined characteristics of the Alpine and Atlantic streamflow spatial patterns. In addition to the above regions, we also identify the scale specific patterns in the Pacific, Indian and Southern Ocean regions at different timescales ranging from seasonal to decadal scale.