Introduction Low back pain (LBP) is recognised globally as a prevalent, costly and disabling condition. Recurrences are common and contribute to much of the burden of LBP. Current evidence favours exercise and education for prevention of LBP recurrence, but an optimal intervention has not yet been established. Walking is a simple, widely accessible, low-cost intervention that has yet to be evaluated. This randomised controlled trial (RCT) aims to establish the effectiveness and cost-effectiveness of a progressive and individualised walking and education programme (intervention) for the prevention of LBP recurrences in adults compared with no treatment (control). Methods and analysis A pragmatic, two-armed RCT comparing walking and education (n=349) with a no treatment control group (n=349). Inclusion criteria are adults recovered from an episode of non-specific LBP within the last 6 months. Those allocated to the intervention group will receive six sessions (three face to face and three telephone delivered) with a trained physiotherapist to facilitate a progressive walking programme and education over a 6-month period. The primary outcome will be days to first recurrence of an episode of activity-limiting LBP. The secondary outcomes include days to recurrence of an episode of LBP, days to recurrence of an episode of LBP leading to care seeking, disability and quality of life measured at 3, 6, 9 and 12 months and costs associated with LBP recurrence. All participants will be followed up monthly for a minimum of 12 months. The primary intention-to-treat analysis will assess difference in survival curves (days to recurrence) using the log-rank statistic. The cost-effectiveness analysis will be conducted from the societal perspective. Ethics and dissemination Approved by Macquarie University Human Research Ethics Committee (Reference: 5201949218164, May 2019). Findings will be disseminated through publication in peer-reviewed journals and conference presentations. Trial registration number ACTRN12619001134112.