The switch from short-term to long-term facilitation of the synapses between sensory and motor neurons mediating gill and tail withdrawal reflexes in Aplysia requires CREB-mediated transcription and new protein synthesis. We isolated several downstream genes, one of which encodes a neuron-specific ubiquitin C-terminal hydrolase. This rapidly induced gene encodes an enzyme that associates with the proteasome and increases its proteolytic activity. This regulated proteolysis is essential for long-term facilitation. Inhibiting the expression or function of the hydrolase blocks induction of long-term but not short-term facilitation. We suggest that the enhanced proteasome activity increases degradation of substrates that normally inhibit long-term facilitation. Thus, through induction of the hydrolase and the resulting up-regulation of the ubiquitin pathway, learning recruits a regulated form of proteolysis that removes inhibitory constraints on long-term memory storage.