Parkinson’s disease (PD) is an incurable condition significantly impacting the quality of life for millions of patients. Much research is devoted to developing early diagnostic tools to ensure symptomatic treatment can start as early as possible. To aid this, here we present a computer vision framework based on automatic gait analysis from a single video camera and evaluate its effectiveness for two challenging datasets containing patients with only “Mild” or “Slight” symptoms. We analyze classification performance using two pose tracking frameworks, six different feature extraction methods, and three classification schemes. In addition, we identify and discuss limitations of a previous approach using Dynamic Time Warping (DTW). Overall, our results show that the gait feature of Margin of Stability allows us to reliably identify PD at 98.8% and 97% accuracy for “Mild” and “Slight” cases, respectively, highlighting its potential usefulness for PD diagnosis.