We focus on the surface urban heat island (SUHI) and the spatiotemporal relationship between land use and surface temperatures (Ts) in Cuiabá-Várzea Grande, Mato Grosso, one of the major urban agglomerations of central-western Brazil, which has suffered intense urbanization processes since the 1960s. Supervised maximum likelihood classifications of optical bands of Landsat Thematic Mapper (Landsat TM) imagery from 1986 and 2007 are applied to generate land use/cover maps. Surface emissivity is determined using the logarithmic transformation of the normalized difference vegetation index. The Ts is retrieved from the thermal bands utilizing a radiative transfer equation. In both cities, urban expansion followed two main development axes, which are reflected in the spatial patterns of Ts. The highest values of Ts were found in bare soil and urbanized areas. Between 1986 and 2007, Ts increased 0.96°C on average and a maximum of 5.49°C in the urban agglomeration. The SUHI in Várzea Grande suffered intensification with an increase of 1.34°C in the downtown area. This tendency was stronger in the center of Cuiabá, where Ts increased 3.12°C. Slowing this rapid rate of temperature increase would demand decisive intervention by municipal authorities, such as restricting annual occupation taxes, reducing the occupation coefficient in new districts, preserving native vegetation, and designating new green areas.