There is a large body of evidence suggesting that cholinergic activity is involved in memory processes. It seems that cholinergic activity is essential to learn several tasks and recent works suggest that acetylcholine plays an important role during the early stages of memory formation. In this review, we will discuss the results related to taste memory formation, focusing particularly on the conditioned taste aversion paradigm. We will first give evidence that nucleus basalis magnocellularis is involved in taste memory formation, due to its cholinergic projections. We then show that the cholinergic activity of the insular (gustatory) cortex is related to the taste novelty, and that the cholinergic signals initiated by novelty are crucial for taste memory formation. Then we present recent data indicating that cortical activation of muscarinic receptors is necessary for taste trace encoding, and also for its consolidation under certain circumstances. Finally, interactions between the cholinergic and other neuromodulatory systems inducing intracellular mechanisms related to plastic changes will be proposed as important processes underlying gustatory memory trace storage.