Stress and drug-associated cues can trigger drug desire and relapse in abstinent cocaine users. Although the role of these two factors in relapse is well documented, it remains unclear as to whether an interaction between stress and drug-associated cues can lead to an enhancement in cocaine-seeking behavior. Here, we assessed the effects of the anxiogenic alpha2-noradrenergic receptor antagonist, yohimbine, on reinstatement of cocaine-seeking in rats either in the presence or absence of cocaine-associated cues. Yohimbine pretreatment in the absence of cocaine-associated cues or cues by themselves reliably reinstated responding on the previously cocaine-paired lever (3-4 times higher than extinction levels). However, animals showed greatly potentiated responding if yohimbine preceded cue-induced reinstatement (10-13 times higher than extinction levels, or 3-5 times over cues or yohimbine alone). While cocaine self-administration produced a significant increase in plasma corticosterone, plasma corticosterone levels did not show a clear relationship to cocaine-paired lever responding during cue and/or yohimbine-induced reinstatement. These results demonstrate that exposure to drug-paired cues during a stressful state can greatly potentiate cocaine-seeking and suggest that future treatment interventions should target multiple modalities.