Background: Staged clinical treatment of pediatric obesity is recommended, but untested. Understanding the lowest intensity stage's effectiveness is necessary for future research. Methods: This was a randomized controlled trial of children ages 4 to <9 years. Participants were recruited after routine evaluations at a primary care pediatric clinic revealed a BMI ≥85th percentile. The intervention was patterned after the "Prevention plus, Stage 1" treatment recommended by an expert committee. Groups were compared for changes, over a 3-month time period, in BMI z-score and parental reports of behavioral issues related to childhood obesity using intent-to-treat (ITT) analysis. Results: Seventy-two (30% of eligible) children were enrolled and 64 were remeasured at 3-month follow-up. ITT analysis revealed that both groups improved mean BMI z-score [adjusted change -0.07, control, and -0.04, intervention; 95% confidence interval (CI) of difference=-0.14-0.20]. Over half of the children in each group improved their BMI z-score (adjusted proportion decreasing=55% in control vs. 72% in intervention; 95% CI of difference=-0.07-0.42). The intervention group improved comparatively to the control group on numerous behavioral indicators. Conclusions: Implementation of the lowest intensity stage of current recommendations is feasible and possibly of benefit toward lifestyle changes. Results of this study can be used by future clinical researchers designing protocols to test the full multi-staged approach for the treatment of pediatric overweight and obesity in primary care clinical settings.