Tobacco use is the largest cause of preventable mortality in the western world. Even after treatment, relapse rates for tobacco are high, and more effective pharmacological treatments are needed. Progesterone (PRO), a female hormone used in contraceptives, reduces stimulant use but its effects on tobacco addiction are unknown. Varenicline (VAR) is a commonly used medication that reduces tobacco use. The present study examined sex differences in the individual vs. combined effects of PRO and VAR on reinstatement of nicotine-seeking behavior in a rat model of relapse. Adult female and male Wistar rats self-administered nicotine (NIC, 0.03 mg/kg/infusion) for 14 days followed by 21 days of extinction when no cues or drug were present. Rats were then divided into 4 treatment groups: control (VEH + SAL), PRO alone (PRO + SAL), VAR alone (VEH + VAR) and the combination (PRO + VAR). Reinstatement of nicotine-seeking behavior induced by priming injections of NIC or caffeine (CAF), presentation of cues (CUES), and the combination of drugs and cues (e.g. NIC + CUES, CAF + CUES) were tested after extinction. Male and female rats did not differ in self-administration of nicotine or extinction responding, and both showed elevated levels of responding to the CAF + CUES condition. However, males, but not females, reinstated active lever-pressing to the NIC + CUES condition, and that was attenuated by both VAR and VAR + PRO treatment. Thus, males were more sensitive to NIC + CUE-induced reinstatement than females, and VAR alone and VAR combined with PRO effectively reduced nicotine relapse.