When encountering a novel problem, individuals explore a solution by testing the effects of potentially relevant options (exploration). Once identifying an appropriate option, they repeatedly choose the option by exploiting their knowledge (exploitation). The ability of humans and animals for strategy switching between exploration and exploitation is crucial for adaptive choice behavior in dynamically changing environments. However, the neuronal mechanism underlying it is poorly understood. To address this issue, we recorded single-unit activity from the dorsal premotor cortex (PMd), one of the cortical areas involved in strategy-guided behavior, while two monkeys performed a trial-and-error visual search task. In this task, since one of six different-color stimuli was associated with reward but not informed to the monkey, the monkey had to search the relevant color by exploration and, after the identification of the color, choose the color repeatedly by exploitation. Additionally, the relevant color was unpredictably changed with no instruction, and thereby the monkey had to explore the color after every color change. Our behavioral data revealed that the monkeys could flexibly switch their strategy between exploration and exploitation during the task. A major part of PMd neurons changed their activity depending on the strategy adopted currently by the monkey. Such activity changes were in a stepwise manner consistent with the behavioral changes. Furthermore, a substantial part of these neurons also exhibited phasic feedback response whose strength accurately predicted strategy switching of the monkey in the next trial. Thus, these results suggest that PMd neurons play a key role in integrating neuronal signals for switching exploratory/exploitative strategy into the internal neural representation of current strategy state to control strategy-guided behavior.