To test the efficacy in promoting brisk walking of two theory-based interventions that incorporate implementation intentions and text message (Short Message Service; SMS) reminders directed at ones walking-related plans or goals. Participants (N = 149) were randomized to one of three conditions (implementation intention + SMS plan reminder, implementation intention + SMS goal reminder, control) before completing measures at baseline and follow-up 4 weeks later. At follow-up, the experimental groups were given a surprise recall task concerning their plans. All participants completed an equivalent goal recall task. Validated self-report measures of physical activity and measures of implementation intention and goal recall, weight, and waist-to-hip ratio. Both intervention groups increased their brisk walking relative to the control group, without reducing other physical activity. The goal reminder group lost the most weight. The SMS plan reminder group recalled more of their plans than the SMS goal reminder group, but the latter were more successful in goal recall. Both interventions can promote brisk walking in sedentary populations. Text messages aid the recall of, and could enhance interventions that target, implementation intentions and goals.