The purpose of this study was to examine the relationship of spirituality, religiosity and self-efficacy with drug and/or alcohol cravings. A cross-sectional survey was completed by 77 male participants at an Australian Salvation Army residential rehabilitation service in 2007. The survey included questions relating to the participants’ drug and/or alcohol use and also measures for spirituality, religiosity, cravings, and self-efficacy. The sample included participants aged between 19 and 74 years, with more than 57% reporting a diagnosis for a mental disorder and 78% reporting polysubstance misuse with alcohol most frequently endorsed as the primary drug of concern (71%). Seventy-five percent of the clients reported that spirituality and religious faith were useful components of the treatment program. A multivariate multiple regression analysis identified that spirituality and self-efficacy have significant relationships with cravings. Self-efficacy mediated the relationship between spirituality and drug and/or alcohol cravings. The limitations of this study included its cross-sectional design and a sample that was drawn from a faith-based program. Future research would benefit from the longitudinal examination of the relationship between spirituality, self-efficacy, and cravings; the exploration of a broader range of client-specific and interpersonal variables; and the inclusion of a control group from a secular treatment facility.