Parkinson’s Disease (PD) is a neurodegenerative disorder that affects, among other things, the gait rhythm. This paper presents an automatic method to identify PD subjects from healthy subjects using information derived from a time series of stride intervals, swing intervals, stance intervals and double support intervals of stride-to-stride measures of footfall contact times using force-sensitive resistors. In our approach, we propose the use of machine learning based classifiers along with features based on metrics of fluctuation magnitude and fluctuation dynamics, obtained from a detrended fluctuation analysis. We evaluate and compare performance of five state-of-the-art classification methods according to their accuracy: Support Vector Machine (SVM), K-Nearest Neighbor (KNN), Naive Bayes (NB), Linear Discriminant Analysis (LDA) and Decision Tree (DT). Our experiments were carried out on a publicly available data base of gait dynamics in neurodegenerative diseases. The results show an average accuracy of 96.8%, representing an improvement compared to other results in the literature. Therefore, the proposed approach presents a path towards an automated, non-invasive and low-cost diagnosis of Parkinson’s Disease.