Up to 70% of cancer survivors report clinically significant levels of fear of cancer recurrence (FCR). Despite the known negative impact of FCR on psychological wellbeing and quality of life, little research has investigated interventions for high FCR. Our team has developed and piloted a novel intervention (Conquer Fear) based on the Self-Regulatory Executive Function Model and Relational Frame Theory and is evaluating Conquer Fear in a randomised controlled trial (RCT). We aim to compare the efficacy and cost-efficacy of the Conquer Fear Intervention and relaxation training in reducing the impact of FCR. This study is a multi-centre RCT with 260 participants randomised either to the Conquer Fear Intervention or relaxation training. Both interventions will be delivered in five sessions over 10 weeks by trained psychologists, psychiatrists and social workers with five or more years experience in oncology. Conquer Fear sessions use attentional training, detached mindfulness, meta-cognitive therapy, values clarification and psycho-education to help patients change the way they regulate and respond to thoughts about cancer recurrence. Relaxation training includes training in progressive and passive muscle relaxation, meditative relaxation, visualisation and “quick relaxation” techniques. Relaxation was chosen to control for therapist time and attention and has good face-validity as an intervention. The primary outcome is fear of cancer recurrence. Secondary outcomes include distress, quality of life, unmet needs, and health care utilisation. Participants complete questionnaires prior to starting the intervention, immediately after completing the intervention, 3 and 6 months later. Eligible participants are early-stage breast or colorectal cancer survivors who have completed hospital-based treatment between 2 months and 5 years prior to study entry and report a score in the clinical range on the Fear of Cancer Recurrence Inventory. The biostatistician is blinded to group allocation and participants are blinded to which intervention is being evaluated. Randomisation is computer generated, stratified by therapist, and uses sequentially numbered sealed envelopes. If successful, the study will provide an evidence-based intervention to reduce psychological morbidity in cancer survivors, and reduce overall health care costs due to more appropriate use of follow-up care and other health services in this very large population. Trial registration: ACTRN12612000404820