Regular physical exercise improves walking performance in patients affected with peripheral obliterative arterial disease (POAD). The mechanisms underlying the phenomenon are still controversial. In order to verify the hypothesis that physical conditioning of lower limbs on a treadmill and ischemic preconditioning of the heart could share some biological aspects, 14 POAD subjects underwent a training program on the treadmill consisting of five repeated submaximal exercises at five-minute and two-hour intervals preceding the maximal tolerance test. Moreover, a protocol with two daily submaximal walking exercises over one week was also performed. Pain-free and total walking distance were measured before and after they performed the program. Moreover, plasma levels of adenosine and adenosine triphosphate (ATP) were measured and polymorphonuclear (PMN) leukocyte activity was studied together with rheologic parameters. Pain-free distance was prolonged by 15.4% and 14.3%, and total distance was prolonged by 23.1% and 26.9%, in the exercises with five-minute and two-hour intervals, respectively. After one week of daily exercises, the onset of pain and the end of the test were delayed by 24% and 43.7%, respectively. An improvement in blood rheology and a reduced PMN reactivity were also observed with the three protocols, associated with an increase in plasma levels of adenosine and ATP. Similarly to ischemic preconditioning in the heart, the possibility is suggested that an adenosine-mediated mechanism may contribute to the development of physical conditioning in treadmill-trained POAD patients.