This study tested the effect of theory-based interventions designed to increase fruit and vegetable intake (FVI). Adults (n = 291) were randomized into four groups: implementation intentions (II) group; self-efficacy (SE) group; combination of implementation intentions and self-efficacy (II+SE) group; and a control group receiving written information on nutrition. They were reassessed at 1, 3, 6 and 12 month follow-up. This study found that short interventions such as SE and II+SE can achieve significant differences in FVI at six-month follow-up compared to the control group. However, this effect was not maintained at 12-month follow-up. Practitioners should add materials or follow up meetings to ensure maintenance of behavioral change.