Child undernutrition in Cambodia is a persistent public health problem requiring low-cost and scalable solutions. Rising cellphone use in low-resource settings represents an opportunity to replace in-person counselling visits with phone calls; however, questions remain on relative effectiveness. Our objective was to evaluate the impact of two options for delivering a World Vision infant and young child feeding (IYCF) counselling programme: (1) traditional Positive Deviance/Hearth (PDH) programme with in-person visits or (2) PDH with Interactive Voice Calling (PDH-IVC) which integrates phone calls to replace 62.5% of face-to-face interaction between caregivers and volunteers, compared to the standard of care (SOC). We conducted a longitudinal cluster-randomised controlled trial in 361 children 6–23 months. We used an adjusted difference-in-difference approach using baseline, midline (3 months) and endline (12 months) surveys to evaluate the impact on child growth among the three groups. At baseline, nearly a third of children were underweight, and over half were food insecure. At midline the PDH group and the PDH-IVC groups had improved weight-for-age z-scores (0.13 DID, p = 0.011; 0.13 DID, p = 0.02, respectively) and weight-for-height z-score (0.16 DID, p = 0.038; 0.24 DID, p = 0.002), relative to SOC. There were no differences in child height-for-age z-scores. At endline, the impact was sustained only in the PDH-IVC group for weight-for-age z-score (0.14 DID, p = 0.049), and the prevalence of underweight declined by 12.8 percentage points (p = 0.036), relative to SOC. Integration of phone-based IYCF counselling is a potentially promising solution to reduce the burden of in-person visits; however, the modest improvements suggest the need to combine it with other strategies to improve child nutrition.