Background: Until a few years ago, Web-based computer-tailored interventions were almost exclusively delivered via computer (eHealth). However, nowadays, interventions delivered via mobile phones (mHealth) are an interesting alternative for health promotion, as they may more easily reach people 24/7. Objective: The first aim of this study was to compare the efficacy of an mHealth and an eHealth version of a Web-based computer-tailored physical activity intervention with a control group. The second aim was to assess potential differences in use and appreciation between the 2 versions. Methods: We collected data among 373 Dutch adults at 5 points in time (baseline, after 1 week, after 2 weeks, after 3 weeks, and after 6 months). We recruited participants from a Dutch online research panel and randomly assigned them to 1 of 3 conditions: eHealth (n=138), mHealth (n=108), or control condition (n=127). All participants were asked to complete questionnaires at the 5 points in time. Participants in the eHealth and mHealth group received fully automated tailored feedback messages about their current level of physical activity. Furthermore, they received personal feedback aimed at increasing their amount of physical activity when needed. We used analysis of variance and linear regression analyses to examine differences between the 2 study groups and the control group with regard to efficacy, use, and appreciation. Results: Participants receiving feedback messages (eHealth and mHealth together) were significantly more physically active after 6 months than participants in the control group (B=8.48, df=2, P=.03, Cohen d=0.27). We found a small effect size favoring the eHealth condition over the control group (B=6.13, df=2, P=.09, Cohen d=0.21). The eHealth condition had lower dropout rates (117/138, 84.8%) than the mHealth condition (81/108, 75.0%) and the control group (91/127, 71.7%). Furthermore, in terms of usability and appreciation, the eHealth condition outperformed the mHealth condition with regard to participants ...