A major limitation of thermal therapies is the lack of detailed thermal information needed to monitor the therapy. Temperatures are routinely measured invasively with thermocouples, but only sparse measurements can be made. Ultrasound tomography is an attractive modality for temperature monitoring because it is non- invasive, non-ionizing, convenient and inexpensive. It capitalizes on the fact that the changes in temperature cause the changes in sound speed. In this work we investigate the possibility of monitoring large temperature changes, in the interval from body temperature to −40◦C. The ability to estimate temperature in this interval is of a great importance in cryosurgery, where freezing is used to destroy abnormal tissue. In our experiment, we freeze locally a tissue-mimicking phantom using a combination of one, two or three cryoprobes. The estimation of sound speed is a difficult task because, first, the sound is highly attenuated when traversing the frozen tissue; and second, the sound speed to be reconstructed has a high spatial bandwidth, due to the dramatic change in speed between the frozen and unfrozen tissue. We show that the first problem can be overcome using a beamforming technique. As the classical reconstruction algorithms inherently smooth the reconstruction, we propose to solve the second problem by applying reconstruction techniques based on sparsity.