Background In the UK just over a fifth of all children start school overweight or obese and overweight 2–5 year olds are at least 4 times more likely to become overweight adults. This can lead to serious future health problems. The WHO have recently highlighted the preschool years as a critical time for obesity prevention, and have recommended preschools as an ideal setting for intervention. However, existing evidence suggests that the preschool environment, including the knowledge, beliefs and practices of preschool staff and parents of young children attending nurseries can be a barrier to the successful implementation of healthy eating interventions in this setting. Methods This study examined the perceptions of preschool centre staff and parents’ of preschool children of healthy eating promotion within preschool settings. The participants were preschool staff working in private and local authority preschool centres in the North East of England, and parents of preschool children aged 3–4 years. Preschool staff participated in semi-structured interviews (n = 16 female, 1 male). Parents completed a mapping activity interview (n = 14 mothers, 1 father). Thematic analysis was applied to interpret the findings. Results Complex communication issues surrounding preschool centre dietary ‘rules’ were apparent. The staff were keen to promote healthy eating to families and felt that parents needed ‘education’ and ‘help’. The staff emphasised that school policies prohibited providing children with sugary or fatty snacks such as crisps, cakes, sweets and ‘fizzy’ drinks, however, some preschool centres appeared to have difficulty enforcing such guidelines. Parents were open to the idea of healthy eating promotion in preschool settings but were wary of being ‘told what to do’ and being thought of as ‘bad parents’. Conclusions There is a need to further explore nursery staff members’ personal perceptions of health and how food policies which promote healthier food in preschool settings can be embedded and implemented. Family friendly healthy eating strategies and activities which utilise nudge theory should be developed and delivered in a manner that is sensitive to parents’ concerns. Preschool settings may offer an opportunity for delivery of such activities.