In vertebrates, several forms of memory-relevant synaptic plasticity involve postsynaptic rearrangements of glutamate receptors. In contrast, previous work indicates that Drosophila and other invertebrates store memories using presynaptic plasticity of cholinergic synapses. Here, we provide evidence for postsynaptic plasticity at cholinergic output synapses from the Drosophila mushroom bodies (MBs). We find that the nicotinic acetylcholine receptor (nAChR) subunit α5 is required within specific MB output neurons for appetitive memory induction but is dispensable for aversive memories. In addition, nAChR α2 subunits mediate memory expression and likely function downstream of α5 and the postsynaptic scaffold protein discs large (Dlg). We show that postsynaptic plasticity traces can be induced independently of the presynapse, and that in vivo dynamics of α2 nAChR subunits are changed both in the context of associative and non-associative (familiarity) memory formation, underlying different plasticity rules. Therefore, regardless of neurotransmitter identity, key principles of postsynaptic plasticity support memory storage across phyla.