Urbanization has a great impact on the local climate of a city, thereby triggering the urban heat island (UHI) effect and affecting the quality of human life. Information on past and present changes of urban landscapes and temperature could be of interest to urban planners in an attempt to shape the urban planning process and mitigate effects of UHI. This study aimed to develop an approach for assessing the urbanization and UHI effects in Ho Chi Minh City (HCMC), Vietnam using Landsat data during the periods 1996–2007–2016. The data were processed through four main steps: (1) data pre-processing, (2) impervious surface (IS) extraction, (3) land surface temperature (LST) retrieval, and (4) accuracy assessment. The results of IS extraction compared with the ground reference data indicated the overall accuracies and Kappa coefficients generally higher than 86.1% and 0.72, in all cases. During 1996–2016, the city was drastically urbanized into multiple directions, with the IS area increasing from 10,488.5 ha (1996) to 27,142.7 ha (2016). The results of retrieved LST revealed the radiant temperature for 1996 ranging from 22.4–35.8 °C, while that for 2016 remarkably higher from 25.3–40.4 °C. The relationship between LST and a newly developed normalized difference composite index (NDCI) was also examined to investigate the genesis of temperature due to decadal urbanization, indicating a strong correlation with the correlation coefficients (r) of higher than 0.71 (p-value < 0.001), in all cases. To further understand UHI impacts due to the urbanization, the proportion of IS and averaged LST over IS areas for each district was calculated. The results showed that only few central districts located in the city higher than 30 °C in 1996, while most of districts were heavily influenced by urban surface structures with the LST higher than 31 °C in 2007 and 32 °C in 2016.