BACKGROUND: HeartSteps is an mHealth intervention that encourages regular walking via activity suggestions tailored to the individuals’ current context. PURPOSE: We conducted a micro-randomized trial (MRT) to evaluate the efficacy of HeartSteps’ activity suggestions to optimize the intervention. METHODS: We conducted a 6-week MRT with 44 adults. Contextually tailored suggestions could be delivered up to five times per day at user-selected times. At each of these five times, for each participant on each day of the study, HeartSteps randomized whether to provide an activity suggestion, and, if so, whether to provide a walking or an antisedentary suggestion. We used a centered and weighted least squares method to analyze the effect of suggestions on the 30-min step count following suggestion randomization. RESULTS: Averaging over study days and types of activity suggestions, delivering a suggestion versus no suggestion increased the 30-min step count by 14% (p = .06), 35 additional steps over the 253-step average. The effect was not evenly distributed in time. Providing any type of suggestion versus no suggestion initially increased the step count by 66% (167 steps; p < .01), but this effect diminished over time. Averaging over study days, delivering a walking suggestion versus no suggestion increased the average step count by 24% (59 steps; p = .02). This increase was greater at the start of study (107% or 271 additional steps; p < .01), but decreased over time. Antisedentary suggestions had no detectable effect on the 30-min step count. CONCLUSION: Contextually tailored walking suggestions are a promising way of initiating bouts of walking throughout the day.