This study assesses the spatial and temporal characteristics of nighttime surface urban heat island (SUHI) effects over Greater Cairo: the largest metropolitan area in Africa. This study employed nighttime land surface temperature (LST) data at 1 km resolution from the Moderate Resolution Imaging Spectroradiometer (MODIS) Aqua sensor for the period 2003–2019. We presented a new spatial anomaly algorithm, which allowed to define SUHI using the most anomalous hotspot and cold spot of LST for each time step over Greater Cairo between 2003 and 2019. Results demonstrate that although there is a significant increase in the spatial extent of SUHI over the past two decades, a significant decrease in the mean and maximum intensities of SUHI was noted. Moreover, we examined the dependency between SUHI characteristics and related factors that influence energy and heat fluxes between atmosphere and land in urban environments (e.g., surface albedo, vegetation cover, climate variability, and land cover/use changes). Results demonstrate that the decrease in the intensity of SUHI was mainly guided by a stronger warming in daytime and nighttime LST in the neighborhood of urban localities. This warming was accompanied by a decrease in surface albedo and diurnal temperature range (DTR) over these areas. Results of this study can provide guidance to local urban planners and decision-makers to adopt more effective mitigation strategies to diminish the negative impacts of urban warming on natural and human environments.