Background: A stepped-down program is one in which clients transition from the care of a health professional to self-managed care. Very little is known about the effectiveness of stepped-down physical activity (PA) programs for military service veterans. Objective: This study will test Active Choices, a stepped-down behavioral support program designed to help Australian Defence Force veterans and their dependents who are clients of the Department of Veterans’ Affairs, transition from treatment by an exercise physiologist or physiotherapist to self-managed PA. Methods: The study is a parallel-group, randomized trial, with city-based exercise physiology or physiotherapy practices that recruit eligible Department of Veterans’ Affairs clients assigned to Active Choices or a comparison program. The study aims to recruit 52 participants (26 in each group). The Active Choices program will consist of 2 face-to-face (Weeks 1, 12) and 2 telephone (Weeks 4 and 8) consultations. During these sessions, the participant and Active Choices consultant will utilize an evidence-based resource booklet to review the key benefits of an active lifestyle, build an action plan for PA preferences, set and review goals, self-monitor progress relative to set goals, and discuss strategies to overcome PA barriers. Linking participants to local PA communities to overcome social isolation will be a program priority. The comparison program will consist of 2 consultations (Weeks 1 and 12) and use fewer behavioral support strategies (education, self-monitoring, and action planning only) than Active Choices. Outcome measures will be administered at baseline, end-intervention (12 weeks), and follow-up (24 weeks) to assess changes in moderate intensity self-managed PA, psychological well-being, and social connectedness. We will also measure health service utilization and costs as well as PA choices across the intervention period. End-intervention interviews will capture participant experiences. Results: Due to the impacts of the COVID-19 pandemic on human research activities in Australia, participant recruitment will commence when it is safe and feasible to do so. Conclusions: Findings will provide valuable pilot data to support up-scaling of the program and larger effectiveness trials with regional and rural as well as city-based Australian Defence Force veterans and their dependents.