Background: Despite established guidelines for regular walking as a first line therapy for adults with peripheral arterial disease (PAD), most patients do not walk routinely. This paper presents the design specifications for a randomized clinical trial to examine the effectiveness of an internet-based walking program compared to a telephone intervention, or the combination (internet-based with telephone counseling) for promotion of regular walking in patients with PAD. Methods: Sedentary adults with documented lower extremity PAD are being recruited from the University of Michigan Health System and the surrounding area. Participants are randomized to one of four arms in a 2 × 2 factorial design: 1) telephone counseling to promote walking, 2) an internet-based walking program with tailored step-count goals, 3) the combination of telephone counseling with the internet-based walking program, or 4) waitlist control. Participants receive a 4-month intervention phase, after which all participants are followed for an additional 8 months to assess long-term adherence to regular walking. Outcomes are assessed at baseline, 4 and 12 months. The primary outcome is walking distance assessed through a standardized treadmill protocol. Additional outcomes include change in step-counts measured with a commercial activity tracker, pain-free walking distance, and changes in health-related quality of life from baseline to follow-up. Conclusion: Finding effective and feasible programs to promote walking among PAD patients is warranted. This study will add to current evidence regarding use of internet based programs with and without telephone counseling to promote regular walking in this population.