A large proportion of adults fail to meet public health guidelines for physical activity as well as fruit, vegetable and fat intake. Interventions are needed to improve these health behaviors. Both computer tailoring and motivational interviewing have shown themselves to be promising techniques for health behavior change. The Vitalum project aims to compare the efficacy of these techniques in improving the health behaviors of adults aged 45-70. This paper describes the design of the Vitalum study. Dutch general medical practices (N = 23) were recruited via a registration network or by personal invitation. The participants were then enrolled through these general practices using an invitational letter. They (n = 2,881) received a written baseline questionnaire to assess health behaviors, and potential psychosocial and socio-demographic behavioral determinants. A power analysis indicated that 1,600 participants who were failing to meet the guidelines for physical activity and either fruit or vegetable consumption were needed. Eligible participants were stratified based on hypertension status and randomized into one of four intervention groups: tailored print communication, telephone motivational interviewing, combined, and control. The first two groups either received four letters or took part in four interviews, whereas the combined group received two letters and took part in two interviews in turns at 5, 13, 30 and 43 weeks after returning the baseline questionnaire. Each letter and interview focused on physical activity or nutrition behavior. The participants also took part in a telephone survey 25 weeks after baseline to gather new information for tailoring. There were two follow-up questionnaires, at 47 and 73 weeks after baseline, to measure short- and long-term effects. The control group received a tailored letter after the last posttest. The process, efficacy and cost-effectiveness of the interventions will be examined by means of multilevel mixed regression, cost-effectiveness analyses and process evaluation. The Vitalum study simultaneously evaluates the efficacy of tailored print communication and telephone motivational interviewing, and their combined use for multiple behaviors and people with different motivational stages and education levels. The results can be used by policymakers to contribute to evidence-based prevention of chronic diseases. Dutch Trial Register NTR1068.