Background: Quality of life (QoL) is a well-established outcome within clinical practice. Despite the adverse effects of substance use disorders on a wide range of patients’ functionality and the multidimensional composition of QoL, the treatment field does not yet systematically assess QoL among patients. Exercise has established positive effects on the QoL of healthy and numerous clinical populations. The potential to integrate exercise within treatment, in order to improve QoL has not been satisfactorily explored. Aims: To measure changes in QoL after group exercise among residential substance use disorder patients and to explore the feasibility of the program within a treatment setting. Methods: We enrolled 35 patients in four long-term residential substance use disorder treatment facilities in Oslo, into a 10-week group exercise program. We analyzed the 24 participants who exercised as completers, while the 11 participants who did not were analyzed as non-completers. We measured QoL, mental distress, somatic health burden and addiction severity at the beginning and end of the program. Results: The program was feasible for participants and the completion rate was 69%. Completers’ physical health domain and psychological health domain of QoL improved significantly. The program engaged the most physically and mentally vulnerable participants, and flexibility and motivational factors were important elements. Conclusions: This study provided promising evidence that low doses of group exercise can yield appreciable benefits, even to patients with more severe health problems.