In human populations, cigarettes and alcohol generally serve as gateway drugs, which people use first before progressing to marijuana, cocaine, or other illicit substances. To understand the biological basis of the gateway sequence of drug use, we developed an animal model in mice and used it to study the effects of nicotine on subsequent responses to cocaine. We found that pretreatment of mice with nicotine increased the response to cocaine, as assessed by addiction-related behaviors and synaptic plasticity in the striatum, a brain region critical for addiction-related reward. Locomotor sensitization was increased by 98%, conditioned place preference was increased by 78%, and cocaine-induced reduction in long-term potentiation (LTP) was enhanced by 24%. The responses to cocaine were altered only when nicotine was administered first, and nicotine and cocaine were then administered concurrently. Reversing the order of drug administration was ineffective; cocaine had no effect on nicotine-induced behaviors and synaptic plasticity. Nicotine primed the response to cocaine by enhancing its ability to induce transcriptional activation of the FosB gene through inhibition of histone deacetylase, which caused global histone acetylation in the striatum. We tested this conclusion further and found that a histone deacetylase inhibitor simulated the actions of nicotine by priming the response to cocaine and enhancing FosB gene expression and LTP depression in the nucleus accumbens. Conversely, in a genetic mouse model characterized by reduced histone acetylation, the effects of cocaine on LTP were diminished. We achieved a similar effect by infusing a low dose of theophylline, an activator of histone deacetylase, into the nucleus accumbens. These results from mice prompted an analysis of epidemiological data, which indicated that most cocaine users initiate cocaine use after the onset of smoking and while actively still smoking, and that initiating cocaine use after smoking increases the risk of becoming dependent on cocaine, consistent with our data from mice. If our findings in mice apply to humans, a decrease in smoking rates in young people would be expected to lead to a decrease in cocaine addiction.