Purpose: To evaluate the long-term effectiveness and cost-effectiveness of a supervised 18-week high-intensity exercise program compared with usual care in patients treated with autologous stem cell transplantation. Methods: One hundred nine patients were randomly assigned to the exercise intervention (n = 54) or the usual care control group (n = 55). Data on cardiorespiratory fitness (VO2peak), handgrip strength, general fatigue, and health-related quality of life (quality-adjusted life years [QALYs]) were collected at baseline (T0), after completion of the exercise intervention or at a similar time point in the control group (T1) and 12 months later (T2). Cost questionnaires were used to assess societal costs. Long-term effectiveness (at T2) was evaluated using linear mixed model analyses. For the economic evaluation, missing data were imputed using multiple imputation, and data were analyzed using linear mixed models. Results: At T2, no statistically significant differences were found between the intervention and control group for VO2peak (0.12; 95%CI − 1.89; 2.14 ml/min/kg), handgrip strength (− 1.08; 95%CI− 2.47; 2.31), and general fatigue (− 0.69; 95%CI − 2.52; 1.14). During 12-months follow-up, no significant between-group differences in QALYs and societal costs were found (QALYs − 0.07; 95%CI − 0.17; 0.04; costs 529; 95%CI − 3205;4452). Intervention costs were €1340 per patient. For all outcomes, the probability of the intervention being cost-effective was low at reasonable values of willingness-to-pay. Conclusion: We found no evidence for the exercise intervention being effective on physical fitness and fatigue, nor cost-effective from a societal perspective. Trial registration: The study was prospectively registered on 27 May 2010 at the Netherlands Trial Register (NTR2341). Implications for Cancer Survivors: The current exercise intervention should not be recommended to patients recently treated with autologous stem cell transplantation.