Nicotine is a major psychoactive and addictive component of tobacco. Although cessation of tobacco use produces various somatic and affective symptoms, withdrawal-related cognitive deficits are considered to be a critical symptom that predict relapse. Therefore, delineating the cognitive mechanisms of nicotine withdrawal may likely provide gainful insights into the neurobiology of nicotine addiction. The present study was designed to examine the effects of nicotine withdrawal induced by mecamylamine, a non-specific nicotinic receptor (nAChR) antagonist, on cognitive control processes in mice using an operant strategy switching task. Brain-derived neurotrophic factor (BDNF) modulates synaptic transmission in frontostriatal circuits, and these circuits are critical for executive functions. Thus, we examined the effects of mecamylamine-precipitated nicotine withdrawal on prefrontal and striatal BDNF protein expression. Mice undergoing precipitated nicotine withdrawal required more trials to attain strategy switching criterion as compared to the controls. Error analysis indicated that impaired performance in these animals was mostly related to their inability to execute the new strategy. The striatal/prefrontal BDNF ratios robustly increased following precipitated nicotine withdrawal. Moreover, higher BDNF ratios were associated with longer task acquisition. Collectively, our findings illustrate that mecamylamine-induced nicotine withdrawal disrupts cognitive control processes and that these changes are possibly linked to perturbations in frontostriatal BDNF signaling.