Rapid urbanization has caused significant land cover change (LCC) as well as changes in the land surface temperature (LST). However, the crucial land dynamic process, which could significantly contribute to the increase in LST and aggravation of the urban heat island (UHI) effect, remains poorly understood. Additionally, a strategy to optimize the most significant decreased land cover type in order to maximize the cooling effect is still lacking. Therefore, in this study, we selected the rapidly urbanizing and ‘hottest’ city in China, Fuzhou, as a case study. Two algorithms were selected to compare and obtain reliable LST data. A land use transfer matrix was used to detect critical contributions leading to the LST variations. The concept of cooling efficiency (CE) and the threshold value of efficiency (TVoE) are also proposed, defined, and calculated. The results show that LST values increased with increasing proportion of built-up land and sharply decreasing proportion of green space. Areas where LST differences exceed 4 °C cover 93% of the areas where green spaces decreased. Additionally, the LST variation is not only associated with the dominant land cover types but is also affected by the land cover transfer pattern and dynamics. Finally, we have calculated the TVoE of green space in Fuzhou city to be 4.55 ± 0.5 ha. This finding implies that when Fuzhou municipality implements urban/landscape planning, a green space area of 4.55 ± 0.5 ha is the most efficient to reduce the heat effect. This study extends the current understanding of LCC dynamics and LST variation. The concepts of the CE and TVoE are meaningful for landscape planning practice and can be used in other cases.