Background: Unhealthy lifestyle behaviours contribute to the poor health of people attending alcohol and other drug (AOD) treatment. Healthy Recovery is an 8-session group-based intervention that targets smoking, diet and physical inactivity as part of an integrated healthy lifestyle approach. The current study aimed to examine the effectiveness of Healthy Recovery when delivered within residential AOD treatment settings. Methods: The study design was a stepped-wedge cluster randomised trial. Participants were 151 current smokers attending residential AOD programs provided by the Australian Salvation Army (n = 71, Control condition; n = 80, Intervention condition). The primary outcome was number of cigarettes smoked per day. Secondary outcomes examined other smoking behaviours (7-day point prevalence, use of nicotine replacement therapy [NRT]), diet (servings and variety of fruit and vegetables), and physical activity. Results: The mean number of cigarettes smoked per day was significantly lower in the Intervention condition at 2-, 5-, and 8-month follow-up. There were also significant differences in favour of the Intervention condition for number of quit attempts, use of NRT and variety of fruit. There were no other significant differences for other dietary or physical activity variables. Conclusions: Healthy Recovery had a positive impact on smoking behaviours. Future research should consider strategies to further promote smoking cessation (e.g. promoting longer-term use of NRT), as well as addressing physical activity and dietary behaviours. The introduction of broader organisational approaches (e.g. smoke free policies, organised group exercise and cooking activities) might help to enhance healthy lifestyle approaches within AOD treatment settings.