The fruit fly Drosophila melanogaster has been successfully used as a model animal for the study of the genetic and molecular mechanisms of learning and memory. Although most of the Drosophila learning studies have used the adult fly, the relative complexity of its neural network hinders cellular and molecular studies at high resolution. In contrast, the Drosophila larva has a simple brain with uniquely identifiable neural networks, providing an opportunity of an attractive alternative system for elucidation of underlying mechanisms involved in learning and memory. In this paper, we describe a novel paradigm of larval associative learning with a single odor and a positive gustatory reinforcer, sucrose. Mutant analyses have suggested importance of cAMP signaling and potassium channel activities in larval learning as has been demonstrated with the adult fly. Intriguingly, larval memory produced by the appetitive conditioning lasts medium term and depends on both amnesiac and cAMP response element-binding protein (CREB). A significant part of memory was disrupted at very early phase by CREB blockade without affecting immediate learning performance. Moreover, we also show that synaptic output of larval mushroom body neurons is required for retrieval but not for acquisition and retention of the larval memory, including the CREB-dependent component.