Deteriorations in both cardiorespiratory fitness (V̇O2peak) and body composition are common following colorectal cancer diagnosis (CRC) and are independently associated with increases in morbidity and mortality. Aerobic exercise training counteracts these effects and therefore can significantly improve clinical prognosis. However the optimal exercise prescription (intensity and frequency) to improve these outcomes in CRC survivors is unknown. This randomised controlled trial investigated the effect of eight weeks of moderate intensity exercise (MIE group; 50min; 70% peak heart rate (HRpeak); 24 sessions), compared to high intensity interval training (HIIT; 4x4min; 85-95% HRpeak) completed at an equivalent (HIIT group; 24 sessions) or tapered frequency (HIIT-T group; 16 sessions) on V̇O2peak and body composition (lean and fat mass). CRC survivors (n=57; intended accrual: n=69) completed V̇O2peak testing and dual-energy x-ray absorptiometry scans of body composition at baseline, 4 and 8 weeks. No severe adverse events occurred. Using mixed effects modeling controlling for baseline values and sex, with Bonferroni adjustments, increases in V̇O2peak were significantly greater following both 4 (+3.0ml.kg-1.min-1 95%CI 0.6-5.3, p=0.008) and 8 (+2.3ml.kg-1.min-1 95%CI 0.0-4.7, p=0.049) weeks of HIIT compared with MIE. After 8 weeks, there was a significantly greater reduction in fat mass in the HIIT compared to the MIE group (-0.7kg 95%CI -1.4--0.03, p=0.038). No significant (p≥0.05) changes in lean mass were observed. Compared to MIE equivalent to the current aerobic exercise recommendations for CRC survivors, HIIT promotes superior improvements in V̇O2peak and fat mass, which are linked to clinically meaningful improvements in CRC morbidity and mortality. Non-significant (p≥0.05) differences between the HIIT and HIIT-T groups across the intervention indicate that prescription of exercise intensity is more important than frequency. Therefore HIIT programs can still elicit clinically relevant improvements in V̇O2peak and fat mass during periods of reduced training frequency, such as interruptions due to commodities, travel or non-adherence.