Objective: Adjuvant protocols devised to enhance motor recovery in subacute stroke patients have failed to show benefits with respect to classic therapeutic interventions. Here, we evaluate the efficacy of a novel brain state–dependent intervention based on known mechanisms of memory and learning that is integrated as part of the weekly rehabilitation program in subacute stroke patients. Methods: Twenty-four hospitalized subacute stroke patients were randomly assigned to 2 intervention groups: (1) the associative group received 30 pairings of a peripheral electrical nerve stimulus (ES) such that the generated afferent volley arrived precisely during the most active phase of the motor cortex as patients attempted to perform a movement; and (2) in the control group, the ES intensity was too low to generate a stimulation of the nerve. Functional (including the lower extremity Fugl–Meyer assessment [LE-FM; primary outcome measure]) and neurophysiological (changes in motor evoked potentials [MEPs]) assessments were performed prior to and following the intervention period. Results: The associative group significantly improved functional recovery with respect to the control group (median [interquartile range] LE-FM improvement = 6.5 [3.5–8.25] and 3 [0.75–3], respectively; p = 0.029). Significant increases in MEP amplitude were seen following all sessions in the associative group only (p ≤ 0.006). Interpretation: This is the first evidence of a clinical effect of a neuromodulatory intervention in the subacute phase of stroke. This was evident with relatively few repetitions in comparison to available techniques, making it a clinically viable approach. The results indicate the potential of the proposed neuromodulation system in daily clinical routine for stroke rehabilitation. Ann Neurol 2018;00:1–12.