Background: Medullary thyroid carcinoma (MTC) in childhood is rare and has an unfavorable prognosis. To improve outcome, early diagnosis is essential. In patients with multiple endocrine neoplasia type 2B (MEN2B), MTC can occur already before the age of 1 year. Recognition of non-endocrine features of MEN2B may lead to timely diagnosis. Purpose: To describe how early recognition of non-endocrine features can lead to a timely diagnosis of MEN2B as well as the effect of recognition of premonitory symptoms on prognosis. Methods: A retrospective case series from the University Medical Center Utrecht/Wilhelmina Children’s Hospital, a Dutch national expertise center for MEN patients. All eight MEN2B patients in follow-up between 1976 and 2020 were included and medical records reviewed. Results: Intestinal ganglioneuromatosis (IGN) as the cause of gastrointestinal (GI) symptoms was detected in seven patients. In three of them within months after birth. This led to early diagnosis of MEN2B, which allowed subsequent curative thyroid surgery. On the contrary, a MEN2B diagnosis later in childhood—in three patients (also) triggered by oral neuromas/neurofibromas—led to recurrent, persistent, and/or progressive MTC in five patients. Conclusions: Neonatal GI manifestations offer the most important window of opportunity for early detection of MEN2B. By accurate evaluation of rectal biopsies in patients with early onset severe constipation, IGN can be timely detected, while ruling out Hirschsprung’s disease. MEN2B gene analysis should follow detection of IGN and—when confirmed—should prompt possibly still curative thyroid surgery.