Cerebellum is a key structure for functional motor recovery after stroke. Enhancing the cerebello-motor pathway by paired associative stimulation (PAS) might improve upper limb function. Here, we conducted a randomized, double-blind, sham-controlled pilot trial investigating the efficacy of a 5-day treatment of cerebello-motor PAS coupled with physiotherapy for promoting upper limb motor function compared to sham stimulation. The secondary objectives were to determine in the active treated group (i) whether improvement of upper limb motor function was associated with changes in corticospinal excitability or changes in functional activity in the primary motor cortex and (ii) whether improvements were correlated to the structural integrity of the input and output pathways. To that purpose, hand dexterity and maximal grip strength were assessed along with TMS recordings and multimodal magnetic resonance imaging, before the first treatment, immediately after the last one and a month later. Twenty-seven patients were analyzed. Cerebello-motor PAS was effective compared to sham in improving hand dexterity (p: 0.04) but not grip strength. This improvement was associated with increased activation in the ipsilesional primary motor cortex (p: 0.04). Moreover, the inter-individual variability in clinical improvement was partly explained by the structural integrity of the afferent (p: 0.06) and efferent pathways (p: 0.02) engaged in this paired associative stimulation (i.e., cortico-spinal and dentato-thalamo-cortical tracts). In conclusion, cerebello-motor-paired associative stimulation combined with physiotherapy might be a promising approach to enhance upper limb motor function after stroke. Clinical Trial Registration URL: http://www.clinicaltrials.gov. Unique identifier: NCT 02284087. Supplementary Information The online version contains supplementary material available at 10.1007/s13311-022-01205-y.