Plastic changes in the efficacy of synapses are widely regarded to represent mechanisms underlying memory formation. So far, evidence for learning-dependent, new neuronal wiring is limited. In this study, we demonstrate that pavlovian eyeblink conditioning in adult mice can induce robust axonal growth and synapse formation in the cerebellar nuclei. This de novo wiring is both condition specific and region specific because it does not occur in pseudoconditioned animals and is particularly observed in those parts of the cerebellar nuclei that have been implicated to be involved in this form of motor learning. Moreover, the number of new mossy fiber varicosities in these parts of the cerebellar nuclei is positively correlated with the amplitude of conditioned eyelid responses. These results indicate that outgrowth of axons and concomitant occurrence of new terminals may, in addition to plasticity of synaptic efficacy, contribute to the formation of memory.