The thermal transport properties of crystalline nanostructures on Si were studied by ultra-fast surface sensitive time-resolved electron diffraction. Self-organized growth of epitaxial Ge hut, dome, and relaxed clusters was achieved by in-situ deposition of 8 monolayers of Ge on Si(001) at 550 °C under UHV conditions. The thermal response of the three different cluster types subsequent to impulsive heating by fs laser pulses was determined through the Debye-Waller effect. Time resolved spot profile analysis and life-time mapping was employed to distinguish between the thermal response of the different cluster types. While dome clusters are cooling with a time constant ofτ = 150 ps, which agrees well with numerical simulations, the smaller hut clusters with a height of 2.3 nm exhibit a cooling time constant ofτ = 50 ps, which is a factor of 1.4 slower than expected.