On a radial temperature gradient, C. elegans worms migrate, after conditioning with food, toward their cultivation temperature and move along this isotherm. This experience-dependent behavior is called isothermal tracking (IT). Here we show that the neuron-specific calcium sensor-1 (NCS-1) is essential for optimal IT. ncs-1 knockout animals show major defects in IT behavior, although their chemotactic, locomotor, and thermal avoidance behaviors are normal. The knockout phenotype can be rescued by reintroducing wild-type NCS-1 into the AIY interneuron, a key component of the thermotaxis network. A loss-of-function form of NCS-1 incapable of binding calcium does not restore IT, whereas NCS-1 overexpression enhances IT performance levels, accelerates learning (faster acquisition), and produces a memory with slower extinction. Thus, proper calcium signaling via NCS-1 defines a novel pathway essential for associative learning and memory.