Walking patterns of persons affected by cerebellar ataxia (CA) are characterized by wide stride-to-stride variability ascribable to: the background pathology-related sensory-motor noise; the motor redundancy, i.e., an excess of elemental degrees of freedom that overcomes the number of variables underlying a specific task performance. In this study, we first tested the hypothesis that healthy and, especially, CA subjects can effectively exploit solutions in the domain of segmental angles to stabilize the position of either the foot or the pelvis (task performance) across heel strikes, in accordance with the uncontrolled manifold (UCM) theory. Next, we verified whether a specific perturbation-based training allows CA subjects to further take advantage of this coordination mechanism to better cope with their inherent pathology-related variability. Results always rejected the hypothesis of pelvis stabilization whereas supported the idea that the foot position is stabilized across heel strikes by a synergic covariation of elevation and azimuth angles of lower limb segments in CA subjects only. In addition, it was observed that the perturbation-based training involves a decreasing trend in the variance component orthogonal to the UCM in both groups, reflecting an improved accuracy of the foot control. Concluding, CA subjects can effectively structure the wide amount of pathology-related sensory-motor noise to stabilize specific task performance, such as the foot position across heel strikes. Moreover, the promising effects of the proposed perturbation-based training paradigm are expected to improve the coordinative strategy underlying the stabilization of the foot position across strides, thus ameliorating balance control during treadmill locomotion.