Background Internationally, the implementation of evidence-based healthy eating policies and practices within early childhood education and care (ECEC) settings that encourage children’s healthy diet is recommended. Despite the existence of evidence-based healthy eating practices, research indicates that current implementation rates are inadequate. Web-based approaches provide a potentially effective and less costly approach to support ECEC staff with implementing nutrition policies and practices. Objective The broad aim of this pilot randomized controlled trial is to assess the feasibility of assessing the impact of a web-based program together with health promotion officer (HPO) support on ECEC center implementation of healthy eating policies and practices. Specifically, we seek to describe the completion rate of study evaluation processes (participant consent and data collection rates); examine ECEC center uptake, acceptability, and appropriateness of the intervention and implementation strategies; understand the potential cost of delivering and receiving implementation support strategies; and describe the potential impact of the web-based intervention on the implementation of targeted healthy eating practices among centers in the intervention group. Methods A 6-month pilot implementation trial using a cluster-randomized controlled trial design was conducted in 22 ECEC centers within the Hunter New England region of New South Wales, Australia. Potentially eligible centers were distributed a recruitment package and telephoned by the research team to assess eligibility and obtain consent. Centers randomly allocated to the intervention group received access to a web-based program, together with HPO support (eg, educational outreach visit and local technical assistance) to implement 5 healthy eating practices. The web-based program incorporated audit with feedback, development of formal implementation blueprints, and educational materials to facilitate improvement in implementation. The centers allocated to the control group received the usual care. Results Of the 57 centers approached for the study, 22 (47%) provided consent to participate. Data collection components were completed by 100% (22/22) of the centers. High uptake for implementation strategies provided by HPOs (10/11, 91% to 11/11, 100%) and the web-based program (11/11, 100%) was observed. At follow-up, intervention centers had logged on to the program at an average of 5.18 (SD 2.52) times. The web-based program and implementation support strategies were highly acceptable (10/11, 91% to 11/11, 100%). Implementation of 4 healthy eating practices improved in the intervention group, ranging from 19% (2/11) to 64% (7/11). Conclusions This study provides promising pilot data to warrant the conduct of a fully powered implementation trial to assess the impact of the program on ECEC healthy eating practice implementation. Trial Registration Australian New Zealand Clinical Trials Registry (ANZCTR) ACTRN12619001158156; https://www.anzctr.org.au/Trial/Registration/TrialReview.aspx?id=378099 International Registered Report Identifier (IRRID) RR2-10.1186/s40814-020-00707-w