Background: Although smartphone apps might support physical activity (PA), engagement with them tends to be low. Objective: This study aimed to examine potential users’ needs and preferences regarding their engagement with PA apps during a first exposure to a never-used PA app and after 2 weeks’ usage. Methods: A longitudinal, one-arm qualitative study was conducted with potential PA app users. At baseline, participants (N=20) were asked to explore 1 of 3 randomly allocated PA apps while thinking aloud. Semistructured interview techniques allowed participants to elaborate on their statements. After 2 weeks, follow-up interviews explored participants’ (n=17) lived experiences of real-world app use. Verbal reports from both time points were analyzed using inductive thematic analysis. Results: Features that promote a fair and simple user experience, support users’ self-regulation skills, and address users’ exercise motives were considered important for engagement both during a first exposure and after a 2-week use of PA apps. Features that support users’ need for relatedness as well as those that facilitate users to implement their intentions were expected to be important for engagement mainly during a first exposure to PA apps. Proactive and tailored features that integrate behavioral, psychological, and contextual information to provide adaptive exercise plans and just-in-time support were considered relevant to sustain engagement over time. Conclusions: App features that address users’ exercise motives, promote self-regulation, and fulfill users’ need for relatedness might promote engagement with PA apps. Tailored and proactive features were expected to promote sustained engagement.