Background Engagement with physical activity mobile apps has been reported to be a core precondition for their effectiveness in digital behavior change interventions. However, to date, little attention has been paid to understanding the perspectives, needs, expectations, and experiences of potential users with physical activity mobile apps. Objective The aim of this study was to investigate the features that are judged to be important for engagement with a physical activity mobile app and the reasons for their importance. Methods A qualitative focus-group methodology with elements of co-design was adopted in this study. Participants reporting sedentary lifestyles and willingness to improve their physical activity behavior through mobile technology were recruited. The focus group sessions consisted of 13 participants (8 men and 5 women, mean [SD] age 41.9 [7.1] years). Two researchers conducted the data analysis independently by using the inductive thematic approach. Results Four main themes emerged in relation to the research question and were named as follows: “physical activity participation motives,” “autonomy and self-regulation,” “need for relatedness,” and “smart.” Additionally, 2 subthemes originated from “physical activity participation motives” (ie, “medical guidance” and “weight loss and fitness for health”) and “smart” (ie, “action planning” and “adaptable and tailored”). Conclusions Features enhancing autonomy and self-regulation and positively affecting health and physical well-being as well as the need for relatedness, adaptability, and flexibility should be considered as core elements in the engagement of potential users with physical activity mobile apps. The emerged findings may orient future research and interventions aiming to foster engagement of potential users with physical activity apps.