Animal brains need to store information to construct a representation of their environment. Knowledge of what happened in the past allows both vertebrates and invertebrates to predict future outcomes by recalling previous experience. Although invertebrate and vertebrate brains share common principles at the molecular, cellular, and circuit-architectural levels, there are also obvious differences as exemplified by the use of acetylcholine versus glutamate as the considered main excitatory neurotransmitters in the respective central nervous systems. Nonetheless, across central nervous systems, synaptic plasticity is thought to be a main substrate for memory storage. Therefore, how brain circuits and synaptic contacts change following learning is of fundamental interest for understanding brain computations tied to behavior in any animal. Recent progress has been made in understanding such plastic changes following olfactory associative learning in the mushroom bodies (MBs) of A current framework of memory-guided behavioral selection is based on the MB skew model, in which antagonistic synaptic pathways are selectively changed in strength. Here, we review insights into plasticity at dedicated MB output pathways and update what is known about the plasticity of both pre- and postsynaptic compartments of MB neurons.