Deep brain stimulation (DBS) relieves motor dysfunction in Parkinson's disease, and other movement disorders. Here, we demonstrate the potential benefits of DBS in a model of ataxia by targeting the cerebellum, a major motor center in the brain. We use the Car8 mouse model of hereditary ataxia to test the potential of using cerebellar nuclei DBS plus physical activity to restore movement. While low-frequency cerebellar DBS alone improves Car8 mobility and muscle function, adding skilled exercise to the treatment regimen additionally rescues limb coordination and stepping. Importantly, the gains persist in the absence of further stimulation. Because DBS promotes the most dramatic improvements in mice with early-stage ataxia, we postulated that cerebellar circuit function affects stimulation efficacy. Indeed, genetically eliminating Purkinje cell neurotransmission blocked the ability of DBS to reduce ataxia. These findings may be valuable in devising future DBS strategies.