Memories are stored in the fan-out fan-in neural architectures of the mammalian cerebellum and hippocampus and the insect mushroom bodies. However, whereas key plasticity occurs at glutamatergic synapses in mammals, the neurochemistry of the memory-storing mushroom body Kenyon cell output synapses is unknown. Here we demonstrate a role for acetylcholine (ACh) in Drosophila. Kenyon cells express the ACh-processing proteins ChAT and VAChT, and reducing their expression impairs learned olfactory-driven behavior. Local ACh application, or direct Kenyon cell activation, evokes activity in mushroom body output neurons (MBONs). MBON activation depends on VAChT expression in Kenyon cells and is blocked by ACh receptor antagonism. Furthermore, reducing nicotinic ACh receptor subunit expression in MBONs compromises odor-evoked activation and redirects odor-driven behavior. Lastly, peptidergic corelease enhances ACh-evoked responses in MBONs, suggesting an interaction between the fast- and slow-acting transmitters. Therefore, olfactory memories in Drosophila are likely stored as plasticity of cholinergic synapses.