Objective: Including partners in interventions to increase physical activity (PA) could promote better adherence and longer-term effects. In preparation for a future large-scale randomized controlled trial (RCT), this randomized pilot trial tested the acceptability of a novel couple-based PA intervention for breast and prostate cancer survivors and the feasibility of conducting an RCT testing the intervention. Method: Twenty cancer survivors (70% female; mean age = 63.0 years, SD = 8.9) and their partners (35% female; mean age = 62.8 years, SD = 7.7) were randomized to either the intervention or waitlist control. Couples in the intervention received four videoconference sessions including training in communication and support skills and behavior change techniques. Measures of PA and partner support for exercise were collected from survivors and partners before randomization and postintervention. Survivors also completed a physical well-being measure, and intervention participants completed a treatment acceptability measure. Results: Recruitment was challenging; approximately 18% of eligible survivors and their partners agreed to participate. Ninety-two percent of randomized participants completed postintervention surveys, and 78% of dyads randomized to the intervention arm completed all 4 sessions. Mean acceptability ratings were moderate to high. Mean difference scores suggested that participants in the intervention arm tended to report greater improvements in PA, partner support, and physical well-being than those in the control arm. Conclusions: These preliminary findings suggest that the couple-based PA intervention was acceptable to survivors and their partners and that a large-scale RCT is likely to be feasible with modified recruitment strategies. Recommendations for improving recruitment and conducting a larger study are presented.