Background: Chemosensory loss is a symptom of Parkinson’s disease starting already at preclinical stages. Their appearance without an identifiable etiology therefore indicates a possible early symptom of Parkinson’s disease. Supervised machine-learning was used to identify parameters that predict Parkinson’s disease among patients having sought medical advice for chemosensory symptoms. Methods: Olfactory, gustatory and demographic parameters were analyzed in 247 patients who had reported for chemosensory symptoms. Unsupervised machine-learning, implanted as so-called fast and frugal decision trees, was applied to map these parameters to a diagnosis of Parkinson’s disease queried for in median 9 years after the first interview. Results: A symbolic hierarchical decision rule-based classifier was created that comprised d = 5 parameters, including scores in tests of odor discrimination, odor identification and olfactory thresholds, the age at which the chemosensory loss has been noticed, and a familial history of Parkinson’s disease. The rule set provided a cross-validated negative predictive performance of Parkinson’s disease of 94.1%; however, its balanced accuracy to predict the disease was only 58.9% while robustly above guessing. Conclusions: Applying machine-learning techniques, a classifier was developed that took the shape of a set of six hierarchical rules with binary decisions about olfaction-related features or a familial burden of Parkinson’s disease. Its main clinical strength lies in the exclusion of the possibility of developing Parkinson’s disease in a patient with olfactory or gustatory loss.