Theoretically driven health communications are needed to promote fruit and vegetable intake among people at different stages of change. The Health Action Process Approach, a clearly specified model and good predictor of fruit and vegetable intake, was used as a framework to guide a formative research for the development of health messages targeting individuals at either a nonintentional or intentional stage of change. A mixed-method approach was used, combining eight focus groups (n=45) and a questionnaire (n=390). Target beliefs for people at both stages were identified under five theoretical constructs (risk perception, outcome expectancies, action planning, coping planning and self-efficacy). Highlighting health problems due to low fruit and vegetable consumption, health benefits, weight reduction and pleasure and enhancing self-efficacy to increase fruit and vegetable intake are the main guidelines for designing messages to non-intenders. For intenders, messages should reassure them of their ability to maintain adequate fruit and vegetable consumption, outline specific plans for increased consumption, identify barriers such as preparation, forgetting or being tired and unwilling to eat fruits and vegetables and suggest strategies to overcome them, such as presenting some practical examples on how to include fruits and vegetables when eating out.