The encoding of long-term associative memories for learned behaviors is a fundamental brain function. Yet, how behavior is stably consolidated and retrieved in the vertebrate cortex is poorly understood. We trained zebrafish in aversive reinforcement learning and measured calcium signals across their entire brain during retrieval of the learned response. A discrete area of dorsal telencephalon that was inactive immediately after training became active the next day. Analysis of the identified area indicated that it was specific and essential for long-term memory retrieval and contained electrophysiological responses entrained to the learning stimulus. When the behavioral rule changed, a rapid spatial shift in the functional map across the telencephalon was observed. These results demonstrate that the retrieval of long-term memories for learned behaviors can be studied at the whole-brain scale in behaving zebrafish in vivo. Moreover, the findings indicate that consolidated memory traces can be rapidly modified during reinforcement learning.