During associative conditioning, animals learn which sensory cues are predictive for positive or negative conditions. Because sensory cues are encoded by distributed neurons, one has to monitor plasticity across many synapses to capture how learned information is encoded. We analyzed synaptic boutons of Kenyon cells of the Drosophila mushroom body γ lobe, a brain structure that mediates olfactory learning. A fluorescent Ca2+ sensor was expressed in single Kenyon cells so that axonal boutons could be assigned to distinct cells and Ca2+ could be measured across many animals. Learning induced directed synaptic plasticity in specific compartments along the axons. Moreover, we show that odor-evoked Ca2+ dynamics across boutons decorrelate as a result of associative learning. Information theory indicates that learning renders the stimulus representation more distinct compared with naive stimuli. These data reveal that synaptic boutons rather than cells act as individually modifiable units, and coherence among them is a memory-encoding parameter.