Purpose: Some religions espouse doctrines that (in)directly impact physical activity (PA) behavior. Yet limited PA interventions have been tailored to religious minorities. Thus, a formative study was conducted to examine the effect of a faith-based pedometer program (Virtual Umra) on psychological correlates of PA behavior and their contribution to school-time changes in PA among Muslim adolescents. Method: Forty-three (27 girls, 16 boys; M[subscript age] = 12.3 ± 1.0 years) students at 1 Islamic middle school participated. Prebaseline and postprogram enjoyment and motivation were measured using the shortened PA Enjoyment Scale and the Situational Motivation Scale, respectively. Pedometer step counts were measured daily during a 2-week baseline and 8 weeks of Virtual Umra. The Reliable Change Index and Cohen's "d" were used to analyze individual-and group-level changes in enjoyment and motivation, respectively. Repeated-measures multivariate analysis of variance (RM-MANOVA) was used to analyze program and gender effects over time. Partial correlations examined the relationships between psychological correlates and PA change. Results: One third of the sample expressed greater enjoyment postprogram ("p" < 0.001, "d" = 0.99), while motivation was unaffected ("p" > 0.05; range, "d" = -0.02 to 0.32). RM-MANOVA revealed that boys increased their steps, whereas girls reduced their step number through the program. Enjoyment increased and extrinsic motivation and amotivation decreased. Partial correlations revealed that enjoyment and more self-determined behavioral regulations were positively associated with non-physical education (PE)-day PA change; only intrinsic motivation was positively associated with PE-day PA change. Conclusion: Virtual Umra was associated with increased enjoyment of PA but needs further modification to more positively impact girls' PA.