BACKGROUND: Physical activity is recommended for people with peripheral arterial disease (PAD), and can improve walking capacity and quality of life; and reduce pain, requirement for surgery and cardiovascular events. This trial will assess the efficacy of a brief behavioral counselling intervention delivered by allied health professionals to improve physical activity in people with PAD. METHODS: This is a multi-center randomised controlled trial in four cities across Australia. Participants (N = 200) will be recruited from specialist vascular clinics, general practitioners and research databases and randomised to either the control or intervention group. Both groups will receive usual medical care, a written PAD management information sheet including advice to walk, and four individualised contacts from a protocol-trained allied health professional over 3 months (weeks 1, 2, 6, 12). The control group will receive four 15-min telephone calls with general discussion about PAD symptoms and health and wellbeing. The intervention group will receive behavioral counselling via two 1-h face-to-face sessions and two 15-min telephone calls. The counselling is based on the 5A framework and will promote interval walking for 3 × 40 min/week. Assessments will be conducted at baseline, and 4, 12 and 24 months by staff blinded to participant allocation. Objectively assessed outcomes include physical activity (primary), sedentary behavior, lower limb body function, walking capacity, cardiorespiratory fitness, event-based claudication index, vascular interventions, clinical events, cardiovascular function, circulating markers, and anthropometric measures. Self-reported outcomes include physical activity and sedentary behavior, walking ability, pain severity, and health-related quality of life. Data will be analysed using an intention-to-treat approach. An economic evaluation will assess whether embedding the intervention into routine care would likely be value for money. A cost-effectiveness analysis will estimate change in cost per change in activity indicators due to the intervention, and a cost-utility analysis will assess change in cost per quality-adjusted life year. A full uncertainty analysis will be undertaken, including a value of information analysis, to evaluate the economic case for further research. DISCUSSION: This trial will evaluate the efficacy and cost-effectiveness of a brief behavioral counselling intervention for a common cardiovascular disease with significant burden. TRIAL REGISTRATION: ACTRN 12614000592640 Australian New Zealand Clinical Trials Registry. Registration Date 4 June 2014.