How learning and memory is controlled at the neural circuit level is a fundamental question in neuroscience. However, molecular and cellular dissection of the neural circuits underlying learning and memory is extremely complicated in higher animals. Here, we report a simple neural circuit for learning behavior in Caenorhabditis elegans, where the calcium-activated phosphatase, calcineurin, acts as an essential modulator. The calcineurin mutant tax-6 showed defective feeding state-dependent learning behavior for temperature and salt. Surprisingly, defective associative learning between temperature and feeding state was caused by malfunctions of two pairs of directly connected interneurons, AIZ and RIA, in the mature nervous system. Monitoring temperature-evoked Ca2+ concentration changes in the AIZ-RIA neural pathway revealed that starvation, a conditioning factor, downregulated AIZ activity through calcineurin during associative learning between temperature and feeding state. Our results demonstrate the molecular and physiological mechanisms of a simple neural circuit for calcineurin-mediated associative learning behavior.