Defining the structural and functional changes in the nervous system underlying learning and memory represents a major challenge for modern neuroscience. Although changes in neuronal activity following memory formation have been studied [B. F. Grewe et al., Nature 543, 670–675 (2017); M. T. Rogan, U. V. Stäubli, J. E. LeDoux, Nature 390, 604–607 (1997)], the underlying structural changes at the synapse level remain poorly understood. Here, we capture synaptic changes in the midlarval zebrafish brain that occur during associative memory formation by imaging excitatory synapses labeled with recombinant probes using selective plane illumination microscopy. Imaging the same subjects before and after classical conditioning at single-synapse resolution provides an unbiased mapping of synaptic changes accompanying memory formation. In control animals and animals that failed to learn the task, there were no significant changes in the spatial patterns of synapses in the pallium, which contains the equivalent of the mammalian amygdala and is essential for associative learning in teleost fish [M. Portavella, J. P. Vargas, B. Torres, C. Salas, Brain Res. Bull. 57, 397–399 (2002)]. In zebrafish that formed memories, we saw a dramatic increase in the number of synapses in the ventrolateral pallium, which contains neurons active during memory formation and retrieval. Concurrently, synapse loss predominated in the dorsomedial pallium. Surprisingly, we did not observe significant changes in the intensity of synaptic labeling, a proxy for synaptic strength, with memory formation in any region of the pallium. Our results suggest that memory formation due to classical conditioning is associated with reciprocal changes in synapse numbers in the pallium.