Patients with substance use disorder (SUD) suffer a higher risk of cardiovascular disease and other lifestyle diseases compared to the general population. High intensity training has been shown to effectively reduce this risk, and therefore we aimed to examine the feasibility and effect of such training in SUD patients in clinical treatment in the present study. 17 males and 7 females (32 ± 8 yr) in treatment were randomized to either a training group (TG), treadmill interval training in 4 × 4 minutes at 90–95% of maximal heart rate, 3 days a week for 8 weeks, or a conventional rehabilitation control group (CG). Baseline values for both groups combined at inclusion were 44 ± 8 (males) and 34 ± 9 (females) mL · min−1 · kg−1, respectively. 9/12 and 7/12 patients completed the TG and CG, respectively. Only the TG significantly improved (15 ± 7%) their maximal oxygen consumption (VO2max), from 42.3 ± 7.2 mL · min−1 · kg−1 at pretest to 48.7 ± 9.2 mL · min−1 · kg−1 at posttest. No between-group differences were observed in work economy, and level of insomnia (ISI) or anxiety and depression (HAD), but a significant within-group improvement in depression was apparent for the TG. High intensity training was feasible for SUD patients in treatment. This training form should be implemented as a part of the rehabilitation since it, in contrast to the conventional treatment, represents a risk reduction for cardiovascular disease and premature death.