Clinically relevant neurological manifestations in children with celiac disease (CD) are unusual, especially when they are considered as signs of the onset of the disease. In this paper, a case of Guillain-Barrè syndrome (GBS) as the first manifestation of CD in a 23-month-old child is reported. We describe a case of CD onset with peripheral neuropathy in a 23-month-old Bulgarian boy presenting with a sudden refusal to walk and absence of deep tendon reflexes in both lower limbs. Neurological symptoms were preceded by two months of gastrointestinal symptoms such as vomiting, abdominal distention, and clear signs of malnutrition and weight loss. When we evaluated the child six months after the onset of the symptoms, clinical and laboratory findings showed clear signs of peripheral neuropathy associated with malnutrition. Serum deamidated gliadin and tissue transglutaminase antibodies were therefore measured. The anti-gliadin levels were more than sixteen times higher than normal and the IgA anti-transglutaminase levels were four times higher than normal. Anti-endomysium antibodies were positive, and human leukocyte antigens (HLA) II typing confirmed a genetic predisposition to CD (DQ2 positive and DQ8 negative). Given the association between the clinical evidence of the disease and the results of the celiac screening tests, a diagnosis of CD was made without biopsy confirmation of the enteropathy. The child began a restricted gluten-free diet that led to complete recovery of the peripheral neuropathy, walking, reflexes, and overall improvement after three months on the diet. Our case underlines the rare but possible associations between CD and peripheral neuropathy in children as an onset symptom, even in the absence of gastrointestinal manifestations, thus suggesting that CD should always be considered in the differential diagnosis of peripheral neuropathy in children. A good knowledge of the extra-intestinal manifestations of CD is essential for the rapid introduction of a gluten-free diet that could be useful for the resolution of the neurological symptoms.