The aim of the study was to investigate the impact of consuming 2 eggs for breakfast 5 days per week compared with eating breakfast cereal in a randomized parallel study. Two energy-restricted diets with a similar energy content were compared over a 6-month period. One hundred and ten participants—aged 56 ± 16 years, BMI 34 ± 6 kg·m2, 84 women and 26 men—commenced and 76 completed the study, 33 in the egg group and 43 in the cereal group. Weight loss in completers was 8.1 kg ± 7.0 kg (8.8 ± 6.4%) in the egg group and 7.3 kg ± 4.0 kg (7.6 ± 4.6%) in the cereal group (p < 0.001 for time) but there was no differential effect of diet (p = 0.56). Vitamin D was 55 ± 18 nmol/L at baseline rose at 3 months and fell at 6 months but remained higher than baseline (p < 0.001 for time) with no difference between the groups. Vitamin D levels were inversely correlated with BMI (r = −0.22 p = 0.025) and positively with age (r = 0.26 p = 0.009), and change in Vitamin D was positively correlated with weight change at 3 and 6 months (r = 0.46 and r = 0.41 both p < 0.001). In a post-hoc analysis of obese participants there was an effect of time (p < 0.01) and a time by diet interaction (p < 0.04), such that participants in the egg group maintained the increase in Vitamin D levels at 6-months. There was no effect on glucose and no adverse effects on total and LDL cholesterol, which did not change. In conclusion, both diets achieved clinically meaningful weight loss. There were no adverse effects on LDL-cholesterol, and there may be a beneficial effect on Vitamin D in people with obesity but this remains to be investigated in a prospective study.