BACKGROUND: Guidelines recommend walking to increase moderate to vigorous physical activity (MVPA) for health benefits. OBJECTIVES: To assess the effectiveness, cost-effectiveness and acceptability of a pedometer-based walking intervention in inactive adults, delivered postally or through dedicated practice nurse physical activity (PA) consultations. DESIGN: Parallel three-arm trial, cluster randomised by household. SETTING: Seven London-based general practices. PARTICIPANTS: A total of 11,015 people without PA contraindications, aged 45-75 years, randomly selected from practices, were invited. A total of 6399 people were non-responders, and 548 people self-reporting achieving PA guidelines were excluded. A total of 1023 people from 922 households were randomised to usual care (n = 338), postal intervention (n = 339) or nurse support (n = 346). The recruitment rate was 10% (1023/10,467). A total of 956 participants (93%) provided outcome data. INTERVENTIONS: Intervention groups received pedometers, 12-week walking programmes advising participants to gradually add '3000 steps in 30 minutes' most days weekly and PA diaries. The nurse group was offered three dedicated PA consultations. MAIN OUTCOME MEASURES: The primary and main secondary outcomes were changes from baseline to 12 months in average daily step counts and time in MVPA (in ≥ 10-minute bouts), respectively, from 7-day accelerometry. Individual resource-use data informed the within-trial economic evaluation and the Markov model for simulating long-term cost-effectiveness. Qualitative evaluations assessed nurse and participant views. A 3-year follow-up was conducted. RESULTS: Baseline average daily step count was 7479 [standard deviation (SD) 2671], average minutes per week in MVPA bouts was 94 minutes (SD 102 minutes) for those randomised. PA increased significantly at 12 months in both intervention groups compared with the control group, with no difference between interventions; additional steps per day were 642 steps [95% confidence interval (CI) 329 to 955 steps] for the postal group and 677 steps (95% CI 365 to 989 steps) for nurse support, and additional MVPA in bouts (minutes per week) was 33 minutes per week (95% CI 17 to 49 minutes per week) for the postal group and 35 minutes per week (95% CI 19 to 51 minutes per week) for nurse support. Intervention groups showed no increase in adverse events. Incremental cost per step was 19p and £3.61 per minute in a ≥ 10-minute MVPA bout for nurse support, whereas the postal group took more steps and cost less than the control group. The postal group had a 50% chance of being cost-effective at a £20,000 per quality-adjusted life-year (QALY) threshold within 1 year and had both lower costs [-£11M (95% CI -£12M to -£10M) per 100,000 population] and more QALYs [759 QALYs gained (95% CI 400 to 1247 QALYs)] than the nurse support and control groups in the long term. Participants and nurses found the interventions acceptable and enjoyable. Three-year follow-up data showed persistent intervention effects (nurse support plus postal vs. control) on steps per day [648 steps (95% CI 272 to 1024 steps)] and MVPA bouts [26 minutes per week (95% CI 8 to 44 minutes per week)]. LIMITATIONS: The 10% recruitment level, with lower levels in Asian and socioeconomically deprived participants, limits the generalisability of the findings. Assessors were unmasked to the group. CONCLUSIONS: A primary care pedometer-based walking intervention in 45- to 75-year-olds increased 12-month step counts by around one-tenth, and time in MVPA bouts by around one-third, with similar effects for the nurse support and postal groups, and persistent 3-year effects. The postal intervention provides cost-effective, long-term quality-of-life benefits. A primary care pedometer intervention delivered by post could help address the public health physical inactivity challenge. FUTURE WORK: Exploring different recruitment strategies to increase uptake. Integrating the Pedometer And Consultation Evaluation-UP (PACE-UP) trial with evolving PA monitoring technologies. TRIAL REGISTRATION: Current Controlled Trials ISRCTN98538934. FUNDING: This project was funded by the National Institute for Health Research (NIHR) Health Technology Assessment programme and will be published in full in Health Technology Assessment; Vol. 22, No. 37. See the NIHR Journals Library website for further project information.