Gait impairment due to neurological disorders is a significant problem around the world. Despite the growing interest in using robotic devices for gait rehabilitation, their widespread use remains limited as there is no clear evidence that robot-assisted gait therapy is superior to traditional treadmill-based therapy. This work is a case study that focuses on investigating the existence of mechanisms of inter-leg coordination after neurological injury, and based on that, proposing novel methods for gait rehabilitation. Using a novel robotic device, the Variable Stiffness Treadmill (VST), we apply perturbations to the compliance of the walking surface underneath the non-paretic leg, and analyze the response of the contralateral (paretic) leg. We show that muscle activity is evoked in the gastrocnemius of the paretic leg. From a clinical prospective, the results of this study can be disruptive because our methods provide a safe and targeted way to provide gait rehabilitation in hemiparesis since direct manipulation of the paretic side is not required. This work provides evidence for the first time that muscle activity can be evoked in the paretic leg of a hemiplegic walker in response to unilateral perturbations to the compliance of the walking surface, providing direction for targeted robot-assisted gait rehabilitation.