A consistent feature of animal locomotion is the capacity to maintain stable movements in changing environments. Here we describe long-term modification of the swing movement of the hind leg in cats in response to repeatedly impeding the movement of the leg. While studying phase transitions in the hind legs, we discovered that repetitively evoking the stumbling-corrective reaction led to long-lasting increases in knee flexion and step height during swing to avoid the impediment. These increases were apparent after approximately 20 stimuli and maximal after about 120 stimuli, and in some animals they persisted for at least 24 hours after presentation of the stimuli. Furthermore, these long-lasting changes were context-dependent and did not generalize to other environments; when walking was observed in an environment distinct from that used in training, the hindlimb kinematics returned to normal. To gain insight into what regions of the nervous system might be involved in this long-term modification, we examined the changes in stepping in decerebrate cats following multiple perturbed steps. In this situation, there was a short-term increase in step height, but this increase was smaller than that evoked in intact animals and it persisted for less than one minute following termination of the stimuli. Thus induction of the long-term increase in step height requires the forebrain. We propose that the conditioned change in leg movement is related to a general ability of animals to adapt locomotor movements to new features of the environment.