Over the last decades, physical inactivity has become one of the leading health risk factors in modern societies. To incentivize people to be more physically active, gamified health behavior change support systems (HBCSSs) are a promising approach. These systems often make use of gamification to keep their users engaged over a sustained period of time. However, despite its popularity, gamification often fails due to insufficient designs, which neglect users’ needs. Building on extant research that investigated users’ preferences in other gamification contexts, we conduct a survey among 447 potential users of HBCSSs for physical activity, using a best-worst-scaling approach. Our results indicate that users generally prefer the game design elements progress, goals, points, and levels, which is partially different from past research on preferred game design elements in other contexts. Thus, our research contributes to the understanding of contextual differences in users’ gamification preferences.