Background: Adolescents with cerebral palsy (CP) who have mobility limitations have almost no access to inexpensive and enjoyable home-based programs that can be disseminated on a large scale to help them independently manage their health through participation in leisure-time physical activity (LTPA). Objective: The primary aim of this study was to determine the preliminary efficacy of the early adoption phase of an adult Movement-to-Music (M2M) program with behavioral telecoaching for increasing LTPA and activity participation compared with a waitlist control group in adolescents with CP. The secondary aim was to explore the effects of the program on perceived levels of pain and fatigue. The tertiary aim was to qualitatively evaluate the factors that influenced adherence and develop a theory that would inform the development of a more targeted M2M telehealth program for this group. Methods: This randomized controlled trial piloted a 4-week M2M program with weekly behavioral telecoaching among 58 adolescents with CP who walked or used wheelchairs. The participants were randomized into one of 2 groups: M2M or control, which maintained their daily activities. M2M included videos that participants were asked to complete 3 times each week at home (asynchronous training). Adherence to video minutes was objectively measured using cloud-based analytics. Changes in activity and LTPA participation were measured before and after the intervention using the Children’s Assessment of Participation and Enjoyment total domain scores and active physical recreation domain scores, respectively. Perceived pain and fatigue were measured using the National Institutes of Health Neuro-QoL short forms. The changes in scores were compared between the groups using analysis of covariance. A grounded theory approach was used to analyze one-on-one interviews, coaching notes, and feedback surveys. Results: A total of 58 people were enrolled, of which 49 (84%) completed the primary outcome follow-up assessment. The mean adherence to the prescribed exercise video minutes across all 4 weeks was 68%, starting from 90% in week 1 and gradually declining to 43% in week 4. Mean adherence to coaching calls was 91%. Analysis of covariance revealed a statistically significant difference between the pre- to postchange scores for Children’s Assessment of Participation and Enjoyment Active Physical Recreation–Intensity domain scores in favor of the intervention group (F1,47=8.76; P=.005; effect size=0.17, also known as volume of LTPA). The qualitative findings highlighted 5 critical factors that influenced participants’ adherence to the program: caregiver support, video elements, suitable exercises, music, and behavioral coaching. Conclusions: This project determined that adolescents with CP responded well to an M2M telehealth program that could enhance their LTPA levels. This paper describes a theory in which adherence to a telehealth LTPA program can be optimized through functional and age-specific modifications for adolescents with CP.