Spouses offer a primary source of support and may provide critical assistance for behavior change. A diet-exercise intervention previously found efficacious in improving cancer survivors’ lifestyle behaviors was adapted to utilize a couples-based approach. The aims were to test the feasibility of this couples-based (CB) intervention and compare its efficacy to the same program delivered to the survivor-only (SO). Twenty-two survivor-spouse couples completed baseline assessments and were randomized to the CB or SO interventions. The study surpassed feasibility benchmarks; 91% of survivors and 86% of spouses completed a 6-month follow-up. Survivors and spouses attended 94% and 91% of sessions, respectively. The SO survivors showed significant improvements on the 30-s chair stand and arm curl tests, weight, and fruit and vegetable (F and V) consumption. The CB survivors showed significant improvements on the 6-min walk and 2-min step tests, body weight, and fat and F and V consumption. Improvement in the 30-s chair stand and arm curl tests was significantly better for SO survivors. The SO spouses showed no significant changes in outcome measures, but the CB spouses showed significant improvements in moderate-to-strenuous physical activity, weight, and fat and F and V consumption. Weight loss was significantly greater in CB spouses compared to SO spouses. Findings demonstrate feasibility, warranting further investigation of CB approaches to promote lifestyle change among cancer survivors and spouses.