Spinal cord injury (SCI) impairs the flow of sensory and motor signals between the brain and the areas of the body located below the lesion level. Here, we describe a neurorehabilitation setup combining several approaches that were shown to have a positive effect in patients with SCI: gait training by means of non-invasive, surface functional electrical stimulation (sFES) of the lower-limbs, proprioceptive and tactile feedback, balance control through overground walking and cue-based decoding of cortical motor commands using a brain-machine interface (BMI). The central component of this new approach was the development of a novel muscle stimulation paradigm for step generation using 16 sFES channels taking all sub-phases of physiological gait into account. We also developed a new BMI protocol to identify left and right leg motor imagery that was used to trigger an sFES-generated step movement. Our system was tested and validated with two patients with chronic paraplegia. These patients were able to walk safely with 65-70% body weight support, accumulating a total of 4,580 steps with this setup. We observed cardiovascular improvements and less dependency on walking assistance, but also partial neurological recovery in both patients, with substantial rates of motor improvement for one of them.