Introduction and Aims: The aim of this study was to explore beliefs about tobacco dependence treatment from the perspective of staff and clients in addiction treatment settings. Design and Methods: A qualitative study was conducted between August and November 2013 using grounded theory methodology. Participants were recruited from four government-funded drug and alcohol services in a regional centre of New South Wales, Australia. Treatment centre staff (n=10) were interviewed using a semistructured interview guide and two focus groups (n=5 and n=6) were held with clients of the same treatment centres. Results: Both clients and staff wish to do more about tobacco use in addiction treatment services, but a number of barriers were identified. Staff barriers included lack of time, tobacco-permissive organisational culture, lack of enforcement of smoke-free policies, beliefs that tobacco is not a treatment priority for clients and that clients need to smoke as a coping strategy, and perceptions that treatment was either ineffective or not used by clients. Clients reported smoking as a habit and for enjoyment or stress relief, seeing staff smoking, nicotine replacement therapy unaffordability and perceptions that nicotine replacement therapy may be addictive, and inability to relate to telephone cessation counselling as barriers to quitting smoking. Discussion and Conclusions: Client and staff perceptions and attitudes about the treatment of tobacco, particularly those relating telephone support and nicotine replacement therapy, provided information, which will inform the design of smoking cessation programs for addiction treatment populations.