Background: Increasing physical activity (PA) in those who have memory concerns requires innovative approaches. Objective: To compare in this randomized controlled trial (RCT) the effects on PA, adherence, and fitness of two approaches to deliver a 6-month home-based PA program in older, inactive individuals at risk of cognitive decline. Methods: Individuals (n = 52) aged 60–85 years, inactive with mild cognitive impairment or subjective cognitive decline were recruited from the community and memory clinics. Randomization was to 6 months of 150 min/week moderate intensity PA with either: goal-setting with mentor support; or education and peer contact. A subset of participants (n = 36) continued for a further 6 months. PA, moderate and vigorous PA, and secondary outcomes, fitness, goal performance/satisfaction and self-efficacy were assessed at baseline, 6 and 12 months. Modelling of primary and secondary outcomes was conducted with linear mixed models. Results: Participants were mean age (±sd) 70.1 (6.4) years. Six-month retention was 88.5%(n = 46). No significant between-group differences were observed for PA or fitness. Post-hoc combined group data showed a significant, moderate-large effect size increase in PA with time. PA increased by a mean 1,662 (943, 2383) steps/day (95%CI) and 1,320 (603, 2037) steps/day at 6 and 12 months (p < 0.001). Median (quartiles Q1-Q3) 6 and 6–12 month combined group adherence was 88.9 (74.4–95.7)%and 84.6 (73.9–95.4)%respectively. Conclusion: In this target group, no differences were detected between groups both intervention strategies were highly effective in increasing PA and fitness.