Parkinson’s disease (PD) is a common neurodegenerative disorder that severely impacts quality of life as the condition progresses. Early diagnosis and treatment is important to reduce burden and costs. Here, we evaluate the diagnostic potential of the Non-Motor symptoms (NMS) questionnaire by the International Parkinson and Movement Disorder Society based on patient-completed answers from a large single-center prospective study. In this study data from 489 study participants consisting of a PD group, a healthy control (HC) group and patients with differential diagnosis (DD) have been recorded with a smartphone-based system. Evaluation of the study data has shown a significant difference in NMS between the representative groups. Cross-validation of Machine Learning based classification achieves balanced accuracy scores of 88.7% in PD vs. HC, 72.1% in PD vs. DD and 82.6% when discriminating between all movement disorders (PD + DD) and the HC group. The results indicate potentially high feature importance of a simple self-administered questionnaire that could support early diagnosis.