Background: We developed an Internet-based physical activity (PA) support program (IPAS), which is embedded in a patient portal. We evaluated the effectiveness and costs of IPAS alone (online only) or IPAS combined with physiotherapist telephone counselling (blended care), compared to a control group. Methods: Breast or prostate cancer survivors, 3–36 months after completing primary treatment, were randomized to 6-months access to online only, blended care, or a control group. At baseline and 6-month post-baseline, minutes of moderate-to-vigorous PA (MVPA) were measured by accelerometers. Secondary outcomes were self-reported PA, fatigue, mood, health-related quality of life, attitude toward PA, and costs. (Generalized) linear models were used to compare the outcomes between groups. Results: We recruited 137 survivors (participation rate 11%). We did not observe any significant between-group differences in MVPA or secondary outcomes. Adherence was rather low and satisfaction scores were low to moderate, with better scores for blended care. Costs for both interventions were low. Conclusions: Recruitment to the study was challenging and the interventions were less efficacious than anticipated, which led to lessons learned for future trials. Suggestions for future research are as follows: improved accessibility of the support program, increased frequency of support, and use of activity trackers.