Perineuronal nets (PNNs) are assemblies of extracellular matrix molecules, which surround the cell body and dendrites of many types of neuron and regulate neural plasticity. PNNs are prominently expressed around neurons of the deep cerebellar nuclei (DCN), but their role in adult cerebellar plasticity and behavior is far from clear. Here we show that PNNs in the mouse DCN are diminished during eyeblink conditioning (EBC), a form of associative motor learning that depends on DCN plasticity. When memories are fully acquired, PNNs are restored. Enzymatic digestion of PNNs in the DCN improves EBC learning, but intact PNNs are necessary for memory retention. At the structural level, PNN removal induces significant synaptic rearrangements in vivo, resulting in increased inhibition of DCN baseline activity in awake behaving mice. Together, these results demonstrate that PNNs are critical players in the regulation of cerebellar circuitry and function.