Purpose: This study evaluated the efficacy of a self-guided Web-based cognitive behaviour therapy (CBT) intervention compared to an attention control in improving cancer-related distress, health-related quality of life (HRQOL), and maladaptive coping, among people recently diagnosed with cancer. Methods: Sixty individuals with cancer diagnosed in the previous 6 months and receiving treatment with curative intent were randomised to receive either the 6-week intervention Cancer Coping Online (CCO: n = 30) or the 6-week Web-based attention control (n = 30). Outcome measures, including cancer distress (the Posttraumatic Stress Scale—Self-Report), general distress (Depression Anxiety Stress Scale), quality of life (EORTC QLQ-C30), and coping (mini-MAC), were administered at baseline, immediately post-intervention, and at 3 and 6 months post-intervention. Results: Significant main effects for time were found for cancer distress, global QOL, physical function, role function, social function, and anxious preoccupation. Post hoc between-group comparisons showed CCO participants had statistically significantly higher physical functioning compared to controls at 3 months of follow-up (d = −0.52, p = 0.02). Furthermore, compared to controls, post hoc comparisons found moderate between-group effect sizes favouring CCO post-intervention for cancer distress (d = 0.43) and anxious preoccupation (d = 0.38), and at 6 months of follow-up for global QOL (d = −0.43). Conclusions: These results provide preliminary support for the potential efficacy of a self-guided Web-based CBT programme in improving aspects of HRQOL, cancer-related distress, and anxious preoccupation after cancer diagnosis. This paper provides justification for, and will help inform the development of, subsequent larger multi-site studies.