The thermal effect of urban impervious surfaces (UIS) is a complex problem. It is thus necessary to study the relationship between UIS and land surface temperatures (LST) using complexity science theory and methods. This paper investigates the long-range cross-correlation between UIS and LST with detrended cross-correlation analysis and multifractal detrended cross-correlation analysis, utilizing data from downtown Shanghai, China. UIS estimates were obtained from linear spectral mixture analysis, and LST was retrieved through application of the mono-window algorithm, using Landsat Thematic Mapper and Enhanced Thematic Mapper Plus data for 1997–2010. These results highlight a positive long-range cross-correlation between UIS and LST across People’s Square in Shanghai. LST has a long memory for a certain spatial range of UIS values, such that a large increment in UIS is likely to be followed by a large increment in LST. While the multifractal long-range cross-correlation between UIS and LST was observed over a longer time period in the W–E direction (2002–2010) than in the N–S (2007–2010), these observed correlations show a weakening during the study period as urbanization increased.