Parkinson’s disease (PD) is a neurodegenerative disease inducing dystrophy of the motor system. Automatic movement analysis systems have potential in improving patient care by enabling personalized and more accurate adjust of treatment. These systems utilize machine learning to classify the movement properties based on the features derived from the signals. Smartphones can provide an inexpensive measurement platform with their built-in sensors for movement assessment. This study compared three feature selection and nine classification methods for identifying PD patients from control subjects based on accelerometer and gyroscope signals measured with a smartphone during a 20-step walking test. Minimum Redundancy Maximum Relevance (mRMR) and sequential feature selection with both forward (SFS) and backward (SBS) propagation directions were used in this study. The number of selected features was narrowed down from 201 to 4–15 features by applying SFS and mRMR methods. From the methods compared in this study, the highest accuracy for individual steps was achieved with SFS (7 features) and Naive Bayes classifier (accuracy 75.3%), and the second highest accuracy with SFS (4 features) and k Nearest neighbours (accuracy 75.1%). Leave-one-subject-out cross-validation was used in the analysis. For the overall classification of each subject, which was based on the majority vote of the classified steps, k Nearest Neighbors provided the most accurate result with an accuracy of 84.5% and an error rate of 15.5%. This study shows the differences in feature selection methods and classifiers and provides generalizations for optimizing methodologies for smartphone-based monitoring of PD patients. The results are promising for further developing the analysis system for longer measurements carried out in free-living conditions.