We tested the effects on problem-solving, anxiety and depression of 12-week group-based self-management cancer rehabilitation, combining comprehensive physical training (PT) and cognitive-behavioural problem-solving training (CBT), compared with PT. We expected that PT + CBT would outperform PT in improvements in problem-solving (Social Problem-Solving Inventory-Revised (SPSI-R)), anxiety and depression (Hospital Anxiety and Depression Scale (HADS)), and that more anxious and/or depressed participants would benefit most from adding CBT to PT. Cancer survivors (aged 48.8 ± 10.9 years, all cancer types, medical treatment completed) were randomly assigned to PT + CBT (n = 76) or PT (n = 71). Measurement occasions were: before and post-rehabilitation (12 weeks), 3- and 9-month follow-up. A non-randomised usual care comparison group (UCC) (n = 62) was measured at baseline and after 12 weeks. Longitudinal intention-to-treat analyses showed no differential pattern in change between PT + CBT and PT. Post-rehabilitation, participants in PT and PT + CBT reported within-group improvements in problem-solving (negative problem orientation; p < 0.01), anxiety (p < 0.001) and depression (p < 0.001), which were maintained at 3- and 9-month follow-up (p < 0.05). Compared with UCC post-rehabilitation, PT and PT + CBT only improved in anxiety (p < 0.05). CBT did not add to the effects of PT and had no extra benefits for higher distressed participants. PT was feasible and sufficient for durably reducing cancer survivors' anxiety.