This randomized trial proposed to determine if there were differences in calf muscle StO(2) parameters in patients before and after 12 weeks of a traditional walking or walking-with-poles exercise program. Data were collected on 85 patients who were randomized to a traditional walking program (n = 40) or walking-with-poles program (n = 45) of exercise training. Patients walked for 3 times weekly for 12 weeks. Seventy-one patients completed both the baseline and the 12-week follow-up progressive treadmill tests (n = 36 traditional walking and n = 35 walking-with-poles). Using the near-infrared spectroscopy measures, StO(2) was measured prior to, during, and after exercise. At baseline, calf muscle oxygenation decreased from 56 ± 17% prior to the treadmill test to 16 ± 18% at peak exercise. The time elapsed prior to reaching nadir StO(2) values increased more in the traditional walking group when compared to the walking-with-poles group. Likewise, absolute walking time increased more in the traditional walking group than in the walking-with-poles group. Tissue oxygenation decline during treadmill testing was less for patients assigned to a 12-week traditional walking program when compared to those assigned to a 12-week walking-with-poles program. In conclusion, the 12-week traditional walking program was superior to walking-with-poles in improving tissue deoxygenation in patients with PAD.