Brain-computer interfaces (BCIs) have the potential to improve functionality in chronic stoke patients when applied over a large number of sessions. Here, we evaluate the effect and the underlying mechanisms of three BCI training sessions in a double-blind-sham-controlled design. The applied BCI is based on Hebbian principles of associativity that hypothesizes that neural assemblies activated in a correlated manner will strengthen synaptic connections. Twenty-two chronic stroke patients were allocated into two training groups. Movement-related cortical potentials (MRCPs) were detected using elecroencephalography during repetitions of foot dorsiflexion. Detection triggered a single electrical stimulation of the common peroneal nerve timed so that the resulting afferent volley arrived at the peak negative phase of the MRCP (BCIassociative group) or randomly (BCInon-associative group). Fugl-Meyer motor assessment (FM), 10-m walking speed, foot and hand tapping frequency and the excitability of the corticospinal tract to the target muscle (tibialis anterior (TA)) were quantified. The TA motor evoked potential increased significantly following the BCIassociative intervention, but not for the BCInon-associative group. Fugl-Meyer motor scores (0.8±0.46 point difference p=0.01), foot (but not finger) tapping frequency, and 10-m walking speed improved significantly for the BCIassociative group, indicating clinically relevant improvements. For the BCI as applied here, the precise coupling between the brain command and the afferent signal was imperative for the behavioral, clinical and neurophysiological changes reported. This association may become the driving principle for the design of BCI rehabilitation in the future. Indeed no available BCIs can match this degree of functional improvement with such a short intervention.