Hebbian spike-timing-dependent plasticity (STDP) is widely observed in organisms ranging from insects to humans and may provide a cellular mechanism for associative learning. STDP requires a millisecond-scale temporal correlation of spiking activity in pre- and postsynaptic neurons. However, animals can learn to associate a sensory cue and a reward that are presented seconds apart. Thus, for STDP to mediate associative learning, the brain must retain information about the sensory cue as spiking activity until the reinforcement signal arrives. In our recent study, we tested this requirement in the moth Manduca sexta. We characterized the odor responses of Kenyon cells, a key neuronal population for insect olfactory learning, and conditioned moths to associate an odor with a sugar water reward. By varying the amount of temporal overlap between odor-evoked spikes and the reward presentation, we found that the most learning occurred when spiking activity had no overlap with the reward presentation; further, increasing the overlap actually decreased the learning efficacy. Thus, STDP alone cannot mediate the olfactory learning in Kenyon cells. Here, we discuss possible cellular mechanisms that could bridge the temporal gap between physiological and behavioral time scales.