Knowledge of the impact of health messages as an intervention strategy is sparse. The aim of this study was to explore recall and use of health behaviour messages among mothers, and whether recall is associated with child health behaviours. Intervention group data from the 15 months Melbourne Infant Feeding, Activity and Nutrition Trial (InFANT) were used (n = 127, children 4 months at commencement). Mothers recalled (unprompted then prompted) at 2 and 3.5 years post-intervention six key messages used in the program, and reported whether they had used them. Children’s food intake was measured by three days of 24-h recall; physical activity by accelerometers; and television viewing by parent report. Unprompted recall ranged between 1–56% across messages and follow-up points, and 37–90% for prompted recall. The most commonly recalled messages “tap into water”, “parents provide, kids decide” and “color every meal with fruit and veg” were also most commonly used. There were few associations between recall and children’s health behaviours. Given the association between recall and reported use, it is important to plan messages so they resonate well with the target group and its needs. Messages should be used as one of multiple strategies within health promotion programs.