Edentulous denture-wearers eat fewer fruits and vegetables than do comparable dentate individuals. Improved chewing ability with new dentures has resulted in little dietary improvement, suggesting that dietary intervention is necessary. The objective of this randomized controlled trial was to have a positive impact upon dietary behavior of patients receiving replacement complete dentures through a tailored dietary intervention. Readiness to change diet (Stage of Change), intake of fruits, vegetables, and nutrients, and chewing ability were assessed pre- and 6 weeks post-intervention. The intervention group (n = 30) received two dietary counseling sessions; the control group (n = 28) received current standard care. Perceived chewing ability significantly increased in both groups. There was significantly more movement from pre-action into action Stages of Change in the intervention group, who had a greater increase in fruit/vegetable consumption (+209 g/d) than did the control group (+26 g/d) (P = 0.001). Tailored dietary intervention contemporaneous with replacement dentures can positively change dietary behavior.