Introduction: Nicotine replacement therapy (NRT) use to support client smoking quit attempts is low and inconsistent at alcohol and other drug (AOD) treatment services. This study examined predictors of any NRT use and combination NRT use among AOD clients who were smokers. Methods: The study was part of a cluster-RCT of an organisational change intervention to introduce smoking cessation support as part of routine treatment in 32 AOD services. The intervention provided AOD services with free NRT and training. Service clients completed baseline (n = 896), 8-week (n = 471) and 6.5-month (n = 427) follow-up surveys. Mixed-model logistic regression examined whether baseline socio-demographic and smoking variables were associated with single and combination NRT use. Results: At 8-weeks follow-up 57% (n = 269/471), and at 6.5-months 33% (n = 143/427) of participants reported using at least one form of NRT. Odds of NRT use at 8-weeks follow-up were greater among participants from treatment vs control group (OR = 3.69, 95%CI 1.8���7.4; p < 0.001), higher vs lower nicotine dependence (OR = 1.74 95%CI 1.1���2.8; p = 0.024), or those motivated to quit (OR = 1.18 95%CI 1.0���1.4; p = 0.017). At 6.5-months, only the treatment arm remained significant. Combination NRT use at the 8-week follow-up was higher among those in treatment vs control group (OR = 2.75 95%CI 1.4���5.6; p = 0.005), or with higher vs lower nicotine dependence (OR = 2.12 95%CI 1.2���3.8; p = 0.014). No factors were associated with combination NRT use at 6.5-months. Conclusions: An organisational change intervention that supplied AOD services with NRT training and products to provide to clients during treatment significantly increases client single form and combination NRT use in the short term.