Memories are thought to be due to lasting synaptic modifications in the brain. The search for memory traces has relied predominantly on determining regions that are necessary for the process. However, a more informative approach is to define the smallest sufficient set of brain structures. The rutabaga adenylyl cyclase, an enzyme that is ubiquitously expressed in the Drosophila brain and that mediates synaptic plasticity, is needed exclusively in the Kenyon cells of the mushroom bodies for a component of olfactory short-term memory. This demonstrates that synaptic plasticity in a small brain region can be sufficient for memory formation.