A highly sensitive fully distributed fiber-optic temperature sensing technique is proposed and demonstrated based on a transient and traveling rocking grating. The rocking grating is generated by pulsed acoustic torsional waves propagating along the fiber. The measured temperature sensitivity is 1000 ppm/°C and is experimentally demonstrated mainly due to the temperature dependence of the fiber birefringence. This traveling rocking grating based sensing technique may also serve other fully-distributed sensing applications by using specially designed fibers.