Conspecific song induces a prompt increase in the expression of the zenk gene in the caudo-medial neostriatum (NCM), a part of the auditory telencephalon of songbirds. To test the hypothesis that zenk gene induction in NCM is related to the acquisition of new song-related memories, we presented adult male zebra finches with repeated playbacks of one song. In response, zenk mRNA levels in NCM increased for the first 30 min, but then declined back to baseline levels despite continued stimulation with the same song. When a novel song was then introduced, however, a full zenk response was triggered once again. Even when a full day had passed between the last exposure to a song and the testing period, the song that had been rendered “familiar#x201D; by repetition caused no zenk response, whereas a novel song caused a full response. Quantitative analysis indicates that individual cells in NCM must have undergone a selective loss in their zenk responsiveness to the repeated song, while still maintaining their ability to respond to the novel song. These results support the hypothesis that the induction of zenk is related to the formation of long-term memories. Analysis of the stimulus-specific modulation of zenk responses, coupled with appropriate behavioral assays, should provide insight into neural mechanisms responsible for the discrimination and storage of complex perceptual information.