Research suggests parental ability to recognise when their child has overweight is limited. It is hypothesised that recognition of child overweight/obesity is fundamental to its prevention, acting as a potential barrier to parental action to improve their child’s health-related behaviours and/or help seeking. The purpose of this study was to investigate the efficacy of an intervention (MapMe) to improve parental ability to correctly categorise their child as having overweight one-month post-intervention, and reduce child body mass index (BMI) z-score 12 months post-intervention. MapMe consists of body image scales of known child BMI and information on the consequences of childhood overweight, associated health-related behaviours and sources of support. We conducted a three-arm (paper-based MapMe, web-based MapMe and control) randomised control trial in fifteen English local authority areas with parents/guardians of 4–5- and 10–11-year-old children. Parental categorisation of child weight status was assessed using the question ‘How would you describe your child’s weight at the moment?’ Response options were: underweight, healthy weight, overweight, and very overweight. Child weight status and BMI z-scores were calculated using objectively measured height and weight data and UK90 clinical thresholds. There was no difference in the percentage of parents correctly categorising their child as having overweight/very overweight (n = 264: 41% control, 48% web-based, and 43% paper-based, p = 0.646). BMI z-scores were significantly reduced for the intervention group at 12 months post-intervention compared to controls (n = 338, mean difference in BMI z-score change −0.11 (95% CI −0.202 to −0.020, p = 0.017). MapMe was associated with a decrease in BMI z-score 12 months post-intervention, although there was no direct evidence of improved parental ability to correctly categorise child overweight status. Further work is needed to replicate these findings in a larger sample of children, investigate mechanisms of action, and determine the use of MapMe as a public health initiative.