Background: Computer-tailored physical activity (PA) interventions delivered through the Internet represent a promising and appealing method to promote PA at a population level. However, personalized advice is mostly provided based on subjectively measured PA, which is not very accurate and might result in the delivery of advice that is not credible or effective. Therefore, an innovative computer-tailored PA advice was developed, based on objectively pedometer-measured PA. Objective: To evaluate the effectiveness of a computer-tailored, pedometer-based PA intervention in working adults. Methods: Participants (≥18 years) were recruited between May 2012 and December 2012 from eight Flemish workplaces. These workplaces were allocated randomly to an intervention or control group. Intervention group participants (n=137) received (1) a booklet with information on how to increase their steps, (2) a non-blinded pedometer and (3) an Internet link to request computer-tailored step advice. Control group participants (n=137) did not receive any of the above mentioned intervention components. Self-reported (IPAQ) and pedometer-based PA were assessed at baseline (T0), and one (T1) and three (T2) months post baseline. Repeated measures analyses of covariance were used to examine intervention effects for both the total sample and the sample at risk (i.e. adults not reaching 10,000 steps a day at baseline). Results: The recruitment process resulted in 274 respondents (response rate of 15%) who agreed to participate. Between T0 and T1 (one-month post baseline), significant intervention effects were found for participants’ daily step counts in both the total sample (P = .004), and the at-risk sample (P = .001). In the sample at risk, the intervention effects showed a daily step count increase of 1056 steps in the intervention group, compared to a decrease of 258 steps in the control group. Comparison of participants’ self-reported PA revealed a significant intervention effect for time spent walking in the at-risk sample (P = .02). Intervention effects were still significant three-months post baseline for participants’ daily step counts in both the total sample (P = .03) and the at-risk sample (P = .02); however, self-reported PA differences were no longer significant. Conclusions: A computer-tailored, pedometer-based PA intervention was effective in increasing both pedometer-based, and self-reported PA levels. However, more efforts should be devoted to recruit and retain participants in order to improve the public health impact of the intervention.