BACKGROUND: Most adults do not achieve the 150 minutes weekly of at least moderate intensity activity recommended for health. Adults' most common physical activity (PA) is walking, light intensity if strolling, moderate if brisker. Pedometers can increase walking; however, most trials have been short-term, have combined pedometer and support effects, and have not reported PA intensity. This trial will investigate whether pedometers, with or without nurse support, can help less active 45-75 year olds to increase their PA over 12 months. DESIGN: Primary care-based 3-arm randomized controlled trial with 12-month follow-up and health economic and qualitative evaluations. PARTICIPANTS: Less active 45-75 year olds (n = 993) will be recruited by post from six South West London general practices, maximum of two per household and households randomised into three groups. Step-count and time spent at different PA intensities will be assessed for 7 days at baseline, 3 and 12 months by accelerometer. Questionnaires and anthropometric assessments will be completed. INTERVENTION: The pedometer-alone group will be posted a pedometer (Yamax Digi-Walker SW-200), handbook and diary detailing a 12-week pedometer-based walking programme, using targets from their baseline assessment. The pedometer-plus-support group will additionally receive three practice nurse PA consultations. The handbook, diary and consultations include behaviour change techniques (e.g., self-monitoring, goal-setting, relapse prevention planning). The control group will receive usual care. OUTCOMES: Changes in average daily step-count (primary outcome), time spent sedentary and in at least moderate intensity PA weekly at 12 months, measured by accelerometry. Other outcomes include change in body mass index, body fat, self-reported PA, quality of life, mood and adverse events. Cost-effectiveness will be assessed by the incremental cost of the intervention to the National Health Service and incremental cost per change in step-count and per quality adjusted life year. Qualitative evaluations will explore reasons for trial non-participation and the interventions' acceptability. DISCUSSION: The PACE-UP trial will determine the effectiveness and cost-effectiveness of a pedometer-based walking intervention delivered by post or practice nurse to less active primary care patients aged 45-75 years old. Approaches to minimise bias and challenges anticipated in delivery will be discussed. TRIAL REGISTRATION: ISRCTN98538934.