Training Aplysia with inedible food for a period that is too brief to produce long-term memory becomes effective in producing memory when training is paired with a nitric oxide (NO) donor. Lip stimulation for the same period of time paired with an NO donor is ineffective. Using qPCR, we examined molecular correlates of brief training versus lip stimulation, of treatment with an NO donor versus saline, and of the combined stimuli producing long-term memory. Changes were examined in mRNA expression of Aplysia homologs of C/EBP, CREB1, CREB1α, CREB1β, and CREB2, in both the buccal and cerebral ganglia controlling feeding. Both the brief training and the NO donor increased expression of C/EBP, CREB1, CREB1α, and CREB1β, but not CREB2 in the buccal ganglia. For CREB1α, there was a significant interaction between the effects of the brief training and of the NO donor. In addition, the NO donor, but not brief training, increased expression of all of the genes in the cerebral ganglion. These findings show that the components of learning that alone do not produce memory produce molecular changes in different ganglia. Thus, long-term memory is likely to arise by both additive and interactive increases in gene expression.