Land surface temperature (LST) serves as an important climate variable which is relevant to a number of studies related to energy and water exchanges, vegetation growth and urban heat island effects. Although LST can be derived from satellite observations, these approaches rely on cloud-free acquisitions. This represents a significant obstacle in regions which are prone to cloud cover. In this paper, a graph-based propagation method, referred to as GraphProp, is introduced. This method can accurately obtain LST values which would otherwise have been missing due to cloud cover. To validate this approach, a series of experiments are presented using synthetically-obscured Landsat acquisitions. The validation takes place over scenarios ranging from between 10% and 90% cloud cover across three urban locations. In presented experiments, GraphProp recovers missing LST values with a mean absolute error of less than 1.1C, 1.0C and 1.8C in 90% cloud cover scenarios across the studied locations respectively.