BACKGROUND: Surgery for colorectal cancer is associated with a high risk of post-operative adverse events, re-operations and a prolonged post-operative recovery. Previously, the effect of prehabilitation (pre-operative physical activity) has been studied for different types of surgery, including colorectal surgery. However, the trials on colorectal surgery have been of limited methodological quality and size. The aim of this trial is to compare the effect of a combined pre- and post-operative intervention of moderate aerobic physical activity and inspiratory muscle training (IMT) with standard care on post-operative recovery after surgery for colorectal cancer. METHODS/DESIGN: We are conducting a randomised, controlled, parallel-group, open-label, multi-centre trial with physical recovery within 4 weeks after cancer surgery as the primary endpoint. Some 640 patients planned for surgery for colorectal cancer will be enrolled. The intervention consists of pre- and post-operative physical activity with increased daily aerobic activity of moderate intensity as well as IMT. In the control group, patients will be advised to continue their normal daily exercise routine. The primary outcome is patient-reported physical recovery 4 weeks post-operatively. Secondary outcomes are length of sick leave, complication rate and severity, length of hospital stay, re-admittances, re-operations, post-operative mental recovery, quality of life and mortality, as well as changes in insulin-like growth factor 1 and insulin-like growth factor-binding protein 3, perception of pain and a health economic analysis. DISCUSSION: An increase in moderate-intensity aerobic physical activity is a safe, cheap and feasible intervention that would be possible to implement in standard care for patients with colorectal cancer. If shown to be effective, this lifestyle intervention could be a clinical parallel to pre-operative smoke cessation that has already been implemented with good clinical results. TRIAL REGISTRATION: ClinicalTrials.gov identifier: NCT02299596 . Registered on 17 November 2014.