Objective: This pilot randomized controlled trial (RCT) aimed at evaluating the feasibility and potential efficacy of a motivational interviewing (MI) intervention to increase physical activity (PA) behavior in cancer patients. Methods: Participants were randomly assigned to an experimental group with standard care plus 12 MI sessions within 12 weeks or a control group with standard care only. The number of recruited participants and the modality of recruitment were recorded to describe the reach of the study. The acceptability of the study was estimated using the attrition rate during the intervention phase. The potential efficacy of the intervention was evaluated by analyzing the PA behavior. Results: Twenty-five participants were recruited within the 16-month recruitment period (1.6 participants per month). Five participants (38.5%) from the experimental group (n = 13) and one participant (8.3%) from the control group (n = 12) dropped out of the study before the end of the intervention phase. No group by time interaction effect for PA behavior was observed at the end of the intervention. Conclusion: Due to the low recruitment rate and compliance, no conclusion can be drawn regarding the efficacy of MI to increase PA behavior in cancer patients. Moreover, the current literature cannot provide any evidence on the effectiveness of MI to increase PA in cancer survivors. Future RCTs should consider that the percentage of uninterested patients to join the study may be as high as 60%. Overrecruitment (30% to 40%) is also recommended to accommodate the elevated attrition rate.