Animals employ diverse learning rules and synaptic plasticity dynamics to record temporal and statistical information about the world. However, the molecular mechanisms underlying this diversity are poorly understood. The anatomically defined compartments of the insect mushroom body function as parallel units of associative learning, with different learning rates, memory decay dynamics and flexibility (Aso and Rubin, 2016). Here, we show that nitric oxide (NO) acts as a neurotransmitter in a subset of dopaminergic neurons in Drosophila. NO’s effects develop more slowly than those of dopamine and depend on soluble guanylate cyclase in postsynaptic Kenyon cells. NO acts antagonistically to dopamine; it shortens memory retention and facilitates the rapid updating of memories. The interplay of NO and dopamine enables memories stored in local domains along Kenyon cell axons to be specialized for predicting the value of odors based only on recent events. Our results provide key mechanistic insights into how diverse memory dynamics are established in parallel memory systems.