Previous models proposed that the subthalamic nucleus (STN) is critical in the early phase of skill acquisition. We hypothesized that subthalamic deep brain stimulation modulates the learning curve in early classification learning. Thirteen idiopathic Parkinson's disease patients (iPD) with subthalamic deep brain stimulation (STN-DBS), 9 medically treated iPD, and 21 age-matched healthy controls were tested with a probabilistic classification task. STN-DBS patients were tested with stimulation OFF and ON, and medically treated patients with medication OFF and ON, respectively. Performance and reaction time were analyzed on the first 100 consecutive trials as early learning phase. Moreover, data were separated for low and high-probability patterns, and more differentiated strategy analyses were used. The major finding was a significant modulation of the learning curve in DBS patients with stimulation ON: although overall learning was similar to healthy controls, only the stimulation ON group showed a transient significant performance dip from trials '41-60' that rapidly recovered. Further analysis indicated that this might be paralleled by a modulation of the learning strategy, particularly on the high-probability patterns. The reaction time was unchanged during the dip. Our study supports that the STN serves as a relay in early classification learning and directs attention toward unacquainted content. The STN might play a role in balancing the short-term success against strategy optimization for improved long-term outcome.