The association of non-motor symptoms (NMSs) with fall-related factors in patients with Parkinson's disease (PD) remains to be further elucidated in the early stages of the disease. Eighty-six patients with less than 5 years of the onset of PD were retrospectively enrolled in the study. We assessed potential fall-related risk factors including (1) a history of falls during the past year (faller versus non-faller), (2) the fear of falling (FoF), and (3) the freezing of gait (FoG). Different types of NMSs were measured using the Montreal Cognitive Assessment (MoCA), the Beck Depression Inventory (BDI), the Beck Anxiety Inventory (BAI), the Parkinson's disease Fatigue Scale (PFS), and the Scales for Outcomes in Parkinson's disease-Autonomic dysfunction (SCOPA-AUT). The faller group (37.2%) showed higher scores for BDI, BAI, PFS, and SCOPA-AUT, compared to the non-faller group. From logistic regression analyses, the prior history of falls was related to the gastrointestinal domain of SCOPA-AUT, FoF was associated with BAI, and gastrointestinal and urinary domains of SCOPA-AUT, and FoG was linked to BAI and gastrointestinal domain of SCOPA-AUT. In conclusion, we found that fall-related risk factors in patients with early PD were highly connected with gastrointestinal dysautonomia.