Objective: It is common for people attending alcohol and other substance dependence treatment to present with multiple unhealthy lifestyle behaviors such as high rates of smoking, physical inactivity, and poor diet. Healthy lifestyle interventions are increasing in importance in the general population, but have been underexamined within alcohol and other substance use populations. The purpose of the current study was to pilot “Healthy Recovery,” a group program that primarily aimed to help people attending alcohol or other substance dependence treatment to reduce or quit smoking. The program also encourages participants to increase physical activity and to eat more servings of fruit and vegetables. Methods: The current study was conducted as a non-randomized controlled pilot trial. All participants were attending residential substance dependence treatment provided by the Australian Salvation Army. In addition to treatment as usual, participants in the treatment condition completed Healthy Recovery (n = 50) and participants in the control group completed an online depression program (n = 27). The study examined the health outcomes of participants (i.e., smoking, physical activity, fruit and vegetable intake, and symptom distress) and the feasibility of running the group sessions within the residential facilities. Results: Within-treatment effects demonstrated medium to large positive effects for reductions in smoking and increases in physical activity, servings of fruit, and servings of vegetables for people completing Healthy Recovery. When compared to the control condition, there were medium effects in favor of the Healthy Recovery condition for reductions in smoking and increases in physical activity. There was a small effect for servings of fruit and no effect for servings of vegetables. Conclusions: Results from this study demonstrated that people attending residential substance dependence treatment are willing and capable of engaging in multiple health behavior change interventions.