Background: Recovery-oriented practice promotes the strengths and recovery potential of individuals. We aimed to establish whether individuals who access mental health services where staff have received the REFOCUS-PULSAR intervention, an adaptation of the UK's REFOCUS recovery-oriented staff intervention for use in Australia, show increased recovery compared with people using non-intervention services. Methods: We did a pragmatic, two-step, stepped-wedge, randomised controlled trial at 18 sites grouped into 14 clusters across public mental health services and mental health community support services in Victoria, Australia. Eligible staff were working part-time or full-time in a direct service role at one of the 18 sites and had consumers being recruited for this study. Eligible consumers were receiving care from a participating cluster, with contact in the 3 months before data collection; aged 18–75 years; and not imprisoned. Clusters were randomly assigned with a web-based randomisation tool to receive the REFOCUS-PULSAR intervention in either the first year (step one) or second year (step two). Consumers, but not staff, were masked to treatment assignment. The primary outcome was the Questionnaire about the Process of Recovery (QPR), for which cross-sectional data were collected across three timepoints (baseline [T0], year 1 [T1], and year 2 [T2]). The primary analysis was done by intention to treat. This trial is registered with ANZCTR, number ACTRN12614000957695. Findings: 190 staff (111 from public mental health services and 79 from mental health community support services) received the REFOCUS-PULSAR recovery-oriented training intervention. Between Sept 18, 2014, and May 19, 2017, 942 consumers were recruited across the three timepoints (T0: n=301; T1: n=334; T2: n=307). The mean QPR score was 53·6 (SD 16·3) in the control group and 54·4 (16·2) in the intervention group (adjusted difference 3·7, 95% CI 0·5–6·8; p=0·023). The Cohen's d value for the intervention effect was small (d=0·23). Interpretation: The REFOCUS-PULSAR intervention had a small but significant effect on the QPRs of individuals using community mental health services and might be effective in promotion of recovery-oriented practice across sectors. Funding: Victorian Government Mental Illness Research Fund.