A randomized two-arm prospective superiority trial tested the efficacy of a novel structured and monitored nutrition (bi-weekly counselling for individualized energy and high dairy protein diet) and exercise program (walking goal of 10,000 steps/day) (intervention) compared to usual care (control) in pregnant women to achieve gestational weight gain (GWG) within current recommendations. Women recruited in communities in southern Ontario, Canada were randomized at 12–17 weeks gestation with stratification by site and pre-pregnancy BMI to intervention (n = 119) or control (n = 122). The primary outcome was the proportion of women who achieved GWG within the Institute of Medicine recommendations. Although the intervention compared to control group was more likely to achieve GWG within recommendations (OR = 1.51; 95% CI (0.81, 2.80)) and total GWG was lower by 1.45 kg (95% CI: (−11.9, 8.88)) neither reached statistical significance. The intervention group achieved significantly higher protein intake at 26–28 week (mean difference (MD); 15.0 g/day; 95% CI (8.1, 21.9)) and 36–38 week gestation (MD = 15.2 g/day; 95% CI (9.4, 21.1)) and higher healthy diet scores (22.5 ± 6.9 vs. 18.7 ± 8.5, p < 0.005) but step counts were similar averaging 6335 steps/day. Pregnancy and infant birth outcomes were similar between groups. While the structured and monitored nutrition with counselling improved diet quality and protein intake and may have benefited GWG, the exercise goal of 10,000 steps/day was unachievable. The results can inform future recommendations for diet and physical activity in pregnancy.