Post-traumatic stress disorder (PTSD) is a devastating disorder with symptoms such as flashbacks, hyperarousal, and avoidance of reminders of the traumatic event. Exposure therapy, which attempts to extinguish fear responses, is a commonly used treatment for PTSD but relapse following successful exposure therapy is a frequent problem. In rodents, spontaneous recovery (SR), where extinguished fear responses resurface following extinction treatment, is used as a model of fear relapse. Previous studies from our lab showed that chronic nicotine impaired fear extinction and acute nicotine enhanced SR of contextual fear in adult male mice. In addition, we showed that acute nicotine’s effects were specific to SR as acute nicotine did not affect recall of contextual fear conditioning in the absence of extinction. However, effects of chronic nicotine administration on SR are not known. Therefore, in the present study, we investigated if chronic nicotine administration altered SR or recall of contextual fear in adult male and female C57BL/6J mice. Our results showed that chronic nicotine significantly enhanced SR in female mice and significantly decreased SR in males. Chronic nicotine had no effect on recall of contextual fear in males or females. Female sham mice also had significantly less baseline SR than male sham mice. Overall, these results demonstrate sex differences in SR of fear memories and that chronic nicotine modulates these effects on SR but nicotine does not alter recall of contextual fear.