Introduction: Patients with colorectal cancer report ongoing physical and psychological impairments and a high proportion of these patients are overweight, insufficiently active and high-risk drinkers, putting them at risk of poor recovery and risk of recurrence and comorbidities. A challenge is implementing sustainable and effective rehabilitation as part of routine care for this group. Methods and analysis: A two-arm pilot randomised controlled trial (RCT) with embedded feasibility study undertaken as a phased programme of work. The intervention involves an existing cardiac rehabilitation programme for cardiac patients accepting colorectal cancer patient referrals. The intervention consists of supervised exercise sessions run by a cardiac physiotherapist and information sessions. Phase 1 will involve one research site enrolling 12 patients to assess intervention and study design processes. Semistructured interviews with patients with colorectal cancer and cardiac patients and clinicians will be used to gather data on acceptability of the intervention and study procedures. Phase 2 will involve three sites enrolling 66 patients with colorectal cancer randomised to control or intervention groups. Outcome measures will be taken preintervention and postintervention, for phases 1 and 2. The primary outcome is accelerometer measured physical activity; secondary outcomes are self-report physical activity, quality of life, anxiety, depression, symptoms including fatigue. The following variables will also be examined to determine if these factors influence adherence and outcomes: self-efficacy, risk perception and treatments. Ethics and dissemination: Full ethical approval was granted by NRES Committees - North of Scotland (13/NS/0004; IRAS project ID: 121757) on 22 February 2013. The proposed work is novel in that it aims to test the feasibility and acceptability of using an evidence-based and theory driven existing cardiac rehabilitation service with patients with colorectal cancer. Should this model of rehabilitation prove to be clinically and cost effective we aim to conduct a randomised controlled trial of this intervention to measure effectiveness. Trial registration reference: ISRCTN63510637; UKCRN id 14092.