Consumption of non-core foods in childhood is associated with excessive weight gain in childhood. Parents play a vital role in establishing healthy diet behaviours in young children. The aim of this study was to assess the effectiveness of a telephone-based intervention in reducing child consumption of non-core foods, and to examine parent and home food environment mediators of change in child consumption. The Healthy Habits trial utilised a clustered randomised controlled design. Parents were recruited from 30 preschools (N=394 participants, mean age 35.2±5.6 years). Parents randomized to the intervention group received four telephone contacts and print materials. Parents allocated to the control condition receive generic print materials only. Non-core food consumption was assessed using a validated child dietary questionnaire at baseline, 2 and 6 months post recruitment in 2010. The intervention was effective in reducing child consumption of non-core foods at 2 months (intention to treat analysis: z=-2.83, p<.01), however this effect was not maintained at 6 months. Structural equation modelling using 2 month data indicated that child access to non-core foods in the home and child feeding strategies mediated the effect of the intervention. The telephone-based intervention shows promise in improving short term dietary behaviour in preschool age children, however further development is needed to sustain the effect in the long-term. Australian Clinical Trials Registry: ACTRN12609000820202.