In this paper, the self-phase modulation (SPM) effect in a double-cladding single-mode tellurite optical fiber (DC-SMTOF) was exploited for temperature sensing. The DC-SMTOF was fabricated based on a TeO2-ZnO-Li2O-Bi2O3 (TZLB) glass material that has a thermo-optical coefficient as high as -16.4×10-6/°C. The temperature sensing performance was evaluated by detecting the 3-dB bandwidth of the SPM spectra with the variation of temperature at different pump wavelength and different average pump power. The temperature sensitivity was obtained to be -2.971 nm/°C with a resolution of 0.0168°C. Both simulation and experiment confirmed that a longer pump wavelength and higher average pump power will result in a higher temperature sensitivity. To the best of our knowledge, this is the first study concerning SPM-based temperature sensing in a tellurite optical fiber. The proposed temperature sensor has a compact structure, and it can realize temperature sensing of high sensitivity without any fiber modification. This work opens the road toward explorations of a novel temperature sensing technology combined with soft glass fibers and nonlinear phenomenon, and is expected to deepen our understanding in the application of these complex nonlinear phenomena.