Background Active transportation (AT; ie, walking and cycling as a mode for transportation) has been associated with decreased morbidity and mortality; however, low-cost and scalable intervention programs are lacking. Objective The goal of the research was to determine the effectiveness of a 3-month behavior change program delivered via a mobile phone app to promote AT (TravelVu Plus) on time spent in moderate-to-vigorous physical activity (MVPA). Methods For this 2-arm parallel randomized controlled trial, we recruited a population-based sample of 254 adults from Stockholm County who were aged 20 to 65 years and had access to a smartphone. On completion of 1-week baseline measures, the 254 participants were randomized to either the control or intervention group (1:1 ratio). Both groups had access to the standard TravelVu app (Trivector AB) for monitoring their AT for 6 months. The intervention group also received a 3-month behavior change program to promote AT (TravelVu Plus app). Assessors of outcomes were blinded to group allocation. Outcomes were objectively measured MVPA at 3 (primary) and 6 months. Secondary outcomes were AT, attitudes toward AT, and health-related quality of life at 3 and 6 months. Results No effect on MVPA was observed after 3 months (P=.29); however, at 6 months the intervention group had a greater improvement in MVPA than the controls (6.05 minutes per day [95% CI 0.36 to 11.74; P=.04]). A Bayesian analyses showed that there was a 98% probability that the intervention had any effect at 6 months, and a 63% probability that this effect was >5 minute MVPA per day. Conclusions No effect on MVPA immediately after the intervention period (at 3 months) was observed; however, there was a delayed effect on MVPA (6 minutes per day) at 6 months, which corresponds to approximately 30% of the weekly MVPA recommendation. Our findings suggest that a behavior change program promoting AT delivered via an app may have a relevant effect on PA. Trial Registration ClinicalTrials.gov NCT03086837; https://clinicaltrials.gov/ct2/show/NCT03086837 International Registered Report Identifier (IRRID) RR2-10.1186/s12889-018-5658-4