Internet-based physical activity (PA) interventions have shown promise, although findings remain equivocal. We used formative research to enhance a previously demonstrated program (Step into Motion) with the goal of developing an Internet program poised for dissemination. We conducted focus groups to identify Internet features targeted to theoretical constructs (social cognitive theory) predictive of PA behavior and rated as "useful for increasing PA." We identified 5 theory-targeted Internet features as useful for increasing PA: (1) a PA tracking/logging calendar targeting self-monitoring and goal setting; (2) geographic mapping tools targeting perceived environment; (3) a discussion forum targeting social support; (4) exercise videos targeting observational learning; and (5) regular updates of peer PA progress targeting situation. We then tested the efficacy of the enhanced program (enhanced Internet, EI; N = 25) in relation to publicly available PA Websites (standard Internet, SI; N = 28) among 53 participants in a randomized controlled trial. The EI arm increased PA in relation to the SI arm at 3 months (18.4 to 186.0 min/wk vs. 20.9 to 57.3 min/wk; p = .03) but between-groups differences were not observed at 6 months (176.8 vs. 133.5 min/wk; p = .44). EI participants maintained PA from 3 to 6 months (186.0 to 176.8 min/wk), and the SI group increased PA (57.3 to 133.5 min/wk). The EI program was efficacious at improving PA levels in relation to publicly available Websites initially, but differences in PA levels were not maintained at 6 months. Future research should identify Internet features that promote long-term maintenance.