Memory storage and memory-related synaptic plasticity rely on precise spatiotemporal regulation of gene expression. To explore the role of small regulatory RNAs in learning-related synaptic plasticity, we carried out massive parallel sequencing to profile the small RNAs of Aplysia californica. We identified 170 distinct miRNAs, 13 of which were novel and specific to Aplysia. Nine miRNAs were brain enriched, and several of these were rapidly downregulated by transient exposure to serotonin, a modulatory neurotransmitter released during learning. Further characterization of the brain-enriched miRNAs revealed that miR-124, the most abundant and well-conserved brain-specific miRNA, was exclusively present presynaptically in a sensory-motor synapse where it constrains serotonin-induced synaptic facilitation through regulation of the transcriptional factor CREB. We therefore present direct evidence that a modulatory neurotransmitter important for learning can regulate the levels of small RNAs and present a role for miR-124 in long-term plasticity of synapses in the mature nervous system.