This paper proposed a quantitative method of land use change trajectory, which means the succession among different land use types across time, to examine the effects of urbanization on an urban heat island (UHI). To accomplish this, multi-temporal images from Landsat 5 Thematic Mapper (TM) and Landsat 7 Enhanced Thematic Mapper Plus (ETM+) of Xiamen City in China from 1987 to 2007 were selected. First, the land use change trajectories were extracted based on the classified images from different years. Then the land surface temperatures (LST) were retrieved and the magnitudes of the UHI were evaluated using the UHI intensity (UHII) indicator. Finally, the indices of the contribution to UHI intensity (CUHII) were constructed and calculated to quantify the effects of each land use change trajectory on the UHI during urbanization. The results demonstrated that the land use change trajectories and CUHII are effective and useful in quantifying the effects of urbanization on UHI. In Xiamen City, a total of 2218 land use change trajectories were identified and 530 of them were the existing urban or urbanization trajectories. The UHII presents a trend of continuous increase from 0.83°C in 1987 to 2.14°C in 2007. With respect to the effects of urban growth on UHI, the contribution of existing urban area to UHI decreased during urbanization. Prior to 2007, the existing urban area of trajectory NO.44444 had the most significant effect on UHI with the greatest CUHII, while the value has decreased from 55.00% in 1987 to 13.03% in 2007 because of the addition of new urbanized area. In 2007, the greatest CUHII was replaced by a trajectory from farmland to built-up area (NO.22224) with the CUHII of 21.98%, followed by the existing urban area of trajectory NO.44444 with the CUHII of 13.03%. These results provide not only a new methodology to assess the environmental effects of urbanization, but also decision-supports for the planning and management of cities.