Abstract Background Mobile health applications (mHealth apps) targeting physical inactivity have increased in popularity yet are usually limited by low engagement. This study examined the impact of adding team-based incentives (Step Together Challenges, STCs) to an existing mHealth app (Carrot Rewards) that rewarded individual physical activity achievements. Methods A 24-week quasi-experimental study (retrospective matched pairs design) was conducted in three Canadian provinces (pre-intervention: weeks 1–12; intervention: weeks 13–24). Participants who used Carrot Rewards and STCs (experimental group) were matched with those who used Carrot Rewards only (controls) on age, gender, province and baseline mean daily step count (±500 steps/d). Carrot Rewards users earned individual-level incentives (worth $0.04 CAD) each day they reached a personalized daily step goal. With a single partner, STC users could earn team incentives ($0.40 CAD) for collaboratively reaching individual daily step goals 10 times in seven days (e.g., Partner A completes four goals and Partner B completes six goals in a week). Results The main analysis included 61,170 users (mean age = 32 yrs.; % female = 64). Controlling for pre-intervention mean daily step count, a significant difference in intervention mean daily step count favoured the experimental group (p < 0.0001; ηp 2 = 0.024). The estimated marginal mean group difference was 537 steps per day, or 3759 steps per week (about 40 walking min/wk). Linear regression suggested a dose-response relationship between the number of STCs completed (app engagement) and intervention mean daily step count (adjusted R2 = 0.699) with each new STC corresponding to approximately 200 more steps per day. Conclusion Despite an explosion of physical activity app interest, low engagement leading to small or no effects remains an industry hallmark. In this paper, we found that adding modest team-based incentives to the Carrot Rewards app increased mean daily step count, and importantly, app engagement moderated this effect. Others should consider novel small-teams based approaches to boost engagement and effects.