Introduction Self-help computer-based programs are easily accessible and cost-effective interventions with a great recruitment potential. However, each program is different and results of meta-analyses may not apply to each new program; therefore, evaluations of new programs are warranted. The aim of this study was to assess the marginal efficacy of a computer-based, individually tailored program (the Coach) over and above the use of a comprehensive Internet smoking cessation website. Methods A two-group randomized controlled trial was conducted. The control group only accessed the website, whereas the intervention group received the Coach in addition. Follow-up was conducted by e-mail after three and six months (self-administrated questionnaires). Of 1120 participants, 579 (51.7%) responded after three months and 436 (38.9%) after six months. The primary outcome was self-reported smoking abstinence over four weeks. Results Counting dropouts as smokers, there were no statistically significant differences between intervention and control groups in smoking cessation rates after three months (20.2% vs. 17.5%, p = 0.25, odds ratio (OR) = 1.20) and six months (17% vs. 15.5%, p = 0.52, OR = 1.12). Excluding dropouts from the analysis, there were statistically significant differences after three months (42% vs. 31.6%, p = 0.01, OR = 1.57), but not after six months (46.1% vs. 37.8%, p = 0.081, OR = 1.41). The program also significantly increased motivation to quit after three months and self-efficacy after three and six months. Discussion An individually tailored program delivered via the Internet and by e-mail in addition to a smoking cessation website did not significantly increase smoking cessation rates, but it increased motivation to quit and self-efficacy.