The ruslan (rus) mutant was previously identified in a behavioral screen for mutants defective in long-lasting memory, which consists of two consolidated memory types, anesthesia-resistant memory, and protein synthesis-dependent long-term memory (LTM). We demonstrate here that rus is a new allele of klingon (klg), which encodes a homophilic cell adhesion molecule. Klg is acutely required for LTM but not anesthesia-resistant memory formation, and Klg expression increases upon LTM induction. LTM formation also requires activity of the Notch cell-surface receptor. Although defects in Notch have been implicated in memory loss because of Alzheimer's disease, downstream signaling linking Notch to memory have not been determined. Strikingly, we found that Notch activity increases upon LTM induction and regulates Klg expression. Furthermore, Notch-induced enhancement of LTM is disrupted by a klg mutation. We propose that Klg is a downstream effector of Notch signaling that links Notch activity to memory.