Human locomotor adaptive learning is thought to involve the cerebellum, but the neurophysiological mechanisms underlying this process are not known. While animal research has pointed to depressive modulation of cerebellar outputs, a direct correlation between adaptive learning and cerebellar depression has never been demonstrated. Here, we used transcranial magnetic stimulation to assess excitability changes occurring in the cerebellum and primary motor cortex (M1) after individuals learned a new locomotor pattern on a split-belt treadmill. To control for potential changes associated to task performance complexity, the same group of subjects was also assessed after performing 2 other locomotor tasks that did not elicit learning. We found that only adaptive learning resulted in reduction of cerebellar inhibition. This effect was strongly correlated with the magnitude of learning (r = 0.78). In contrast, M1 excitability changes were not specific to learning but rather occurred in association with task complexity performance. Our results demonstrate that locomotor adaptive learning in humans is proportional to cerebellar excitability depression. This finding supports the theory that adaptive learning is mediated, at least in part, by long-term depression in Purkinje cells. This knowledge opens the opportunity to target cerebellar processes with noninvasive brain stimulation to enhance motor learning.