Background: Cancer patients experience significant distress throughout treatment and especially during transition back to normal life with greater burden on socially disadvantaged patients and those with medical comorbidities. Patient stressors can interfere with their ability to make reasoned and timely decisions about survivorship care and lead to poor quality of life and low physical and social functioning. This pilot effectiveness-implementation study examined the impact and feasibility of offering the Bright IDEAS system of Problem-Solving Skills Training (PSST) to adult cancer survivors to help them and their caregivers cope more successfully with decision making and distress. Methods: Patients with breast (21), prostate (9) or colorectal (20) cancer who completed their definitive cancer treatment within the last 6 months and had their cancer survivorship visit were recruited from two regional cancer centers and affiliated community oncology clinics. Patients with an NCCN distress level > 2 were randomly assigned to either care as usual (CAU) or 8 weekly PSST sessions provided by a trained therapist in person or remotely. Patients were invited but not required to include a supportive other (n = 17). Patient and caregiver assessments at baseline (T1), end of intervention/3 months (T2), and 3 months post intervention/6 months (T3) focused on problem-solving skills (SPSI-25), distress (HADS) and quality of life (FACT). We also collected healthcare utilization data. We compared outcome changes T1-T2 and T1-T3, by study arm, using t-tests. Multivariate regression analysis identified subgroups of patients with positive and negative responses to skills training. Results: Average age of the participants was 63 years (45 to 87) with racial and ethnic distributions representative of the local population (88% white). Two thirds were women (n = 32), one third of the patients were recruited and received therapy fully remotely due to COVID-19-related protocol changes. Patients who received PSST reported a reduction in dysfunctional problem-solving style and improvement in constructive style while problem-solving skills of CAU patients trended in the opposite direction. Patients in the PSST arm also reported significant reduction in anxiety and depression and improvement in cancer-specific quality of life (p < 0.05) that was sustained at 6 months. Patients in the PSST arm reported lower use of hospital and ED services compared to CAU patients (p = 0.07). Better improvement in outcomes was driven by lower problem-solving skills at baseline. Conclusions: Despite the logistical complexity of running a clinical trial during quarantine, patients and caregivers in the PSST arm demonstrated meaningful improvement in distress and quality of life. The evidence from this pilot study will help guide development of a future multi-site randomized clinical trial of the effect of PSST on cancer survivorship care and outcomes. Clinical trial information: NCT03567850