Background: Supervised treadmill-walking exercise programs have been proven to be a highly effective in improving walking distance in peripheral arterial disease (PAD) patients with lifestyle-limiting claudication. Limited information is available on the contributions of central cardiorespiratory functions for improving these patients' walking capacity with exercise training. Methods: This study randomized 28 participants (21 men; age, 65.6 years; 92.7% smoking history, 36.6% with diabetes) with lifestyle-limiting PAD-related claudication to 3 hours/week of supervised exercise training for 12 weeks, using arm-ergometry (n = 10) or treadmill-walking (n = 10) vs a usual-care control group (n = 8). Cardiorespiratory function measurements were assessed before and after training at a submaximal workload and at the onset of claudication (pain-free walking distance [PFWD]) and at maximal walking distance [(MWD]). Changes in these functions from baseline were analyzed among the groups with analysis of covariance. Associations between variables were determined by Pearson's partial correlations. Results: The mean baseline demographic, medical, and exercise variables were similar among the groups. There were similar significant differences in the submaximal double product (heart rate × systolic blood pressure) and at MWD, ventilatory threshold, ventilatory oxygen uptake (VO2) at onset of claudication, and VO2 peak in response to training in both exercise groups vs the control group. Statistically significant, moderate correlations (r = 0.60-0.68) were found between changes in all cardiorespiratory variables and changes in PFWD or MWD. Conclusion: Improvements in cardiorespiratory function after arm-ergometry or treadmill-training were significantly associated with improvements in both PFWD and MWD, providing supporting evidence of systemic contributions to exercise training-related improvements in walking capacity seen in patients with claudication.