Nicotine withdrawal is associated with numerous symptoms including impaired hippocampus-dependent learning. Theories of nicotine withdrawal suggest that nicotinic acetylcholine receptors (nAChRs) are hypersensitive during withdrawal, which suggests enhanced sensitivity to nicotine challenge. Research indicates that prior exposure to nicotine enhances sensitivity to nicotine challenge, but it is unclear if this is due to prior nicotine exposure or specific to nicotine withdrawal. Therefore, the present experiments examined if prior nicotine exposure or nicotine withdrawal altered the effects of nicotine challenge on hippocampus-dependent learning. C57BL/6J mice were trained and tested in contextual conditioning following saline or nicotine challenge either during (24 h after cessation) or after (14 days after cessation) a period of nicotine withdrawal symptoms. Nicotine challenge produced a greater enhancement of contextual conditioning relative to control withdrawal state in mice withdrawn from chronic nicotine for 24 h compared to 14 days and corresponding saline controls. These experiments support the suggestion that during periods of abstinence, smokers may perceive tobacco providing a large boost in cognition.