Caenorhabditis elegans navigates thermal gradients by using a behavioral strategy that is regulated by a memory of its cultivation temperature (T(c)). At temperatures above or around the T(c), animals respond to temperature changes by modulating the rate of stochastic reorientation events. The bilateral AFD neurons have been implicated as thermosensory neurons, but additional thermosensory neurons are also predicted to play a role in regulating thermotactic behaviors. Here, we show that the AWC olfactory neurons respond to temperature. Unlike AFD neurons, which respond to thermal stimuli with continuous, graded calcium signals, AWC neurons exhibit stochastic calcium events whose frequency is stimulus-correlated in a T(c)-dependent manner. Animals lacking the AWC neurons or with hyperactive AWC neurons exhibit defects in the regulation of reorientation rate in thermotactic behavior. Our observations suggest that the AFD and AWC neurons encode thermal stimuli via distinct strategies to regulate C. elegans thermotactic behavior.