Parkinson’s disease (PD) is a neurological condition that is chronic and worsens over time, which presents a challenging diagnosis. An accurate diagnosis is required to recognize PD patients from healthy individuals. Diagnosing PD at early stages can reduce the severity of this disorder and improve the patient’s living conditions. Algorithms based on associative memory (AM) have been applied in PD diagnosis using voice samples of patients with this health condition. Even though AM models have achieved competitive results in PD classification, they do not have any embedded component in the AM model that can identify and remove irrelevant features, which would consequently improve the classification performance. In this paper, we present an improvement to the smallest normalized difference associative memory (SNDAM) algorithm by means of a learning reinforcement phase that improves classification performance of SNDAM when it is applied to PD diagnosis. For the experimental phase, two datasets that have been widely applied for PD diagnosis were used. Both datasets were gathered from voice samples from healthy people and from patients who suffer from this condition at an early stage of PD. These datasets are publicly accessible in the UCI Machine Learning Repository. The efficiency of the ISNDAM model was contrasted with that of seventy other models implemented in the WEKA workbench and was compared to the performance of previous studies. A statistical significance analysis was performed to verify that the performance differences between the compared models were statistically significant. The experimental findings allow us to affirm that the proposed improvement in the SNDAM algorithm, called ISNDAM, effectively increases the classification performance compared against well-known algorithms. ISNDAM achieves a classification accuracy of 99.48%, followed by ANN Levenberg–Marquardt with 95.89% and SVM RBF kernel with 88.21%, using Dataset 1. ISNDAM achieves a classification accuracy of 99.66%, followed by SVM IMF1 with 96.54% and RF IMF1 with 94.89%, using Dataset 2. The experimental findings show that ISNDAM achieves competitive performance on both datasets and that statistical significance tests confirm that ISNDAM delivers classification performance equivalent to that of models published in previous studies.