Relapse to drug abuse is often caused by exposure to drug-associated cues that evoke craving. Therefore, disruption of the cue-drug memory can prevent relapse. Memories destabilize and become temporarily labile upon their retrieval, and re-stabilize in a process termed reconsolidation. Pharmacological disruption of reconsolidation prevents relapse in animal models, yet may evoke side effects. Therefore, behavioral procedures capable of preventing cue-induced craving and relapse are extremely valuable. Aversion therapies, in which drug-paired cues are re-associated (counterconditioned) with aversive consequences, have limited success, because the previous cue-drug memory may recover, triggering relapse. Here, we prevented the memory recovery and relapse to cocaine seeking by applying aversive counterconditioning during memory reconsolidation. Mice were trained to seek cocaine in a conditioned place preference procedure. The cocaine-associated compartment was then counterconditioned with lithium chloride (LiCl)-induced malaise, preceded by a brief exposure to the compartment (memory retrieval). Relapse was assessed in a reinstatement test. We found that aversive counterconditioning conducted shortly after memory retrieval (during reconsolidation) induced a long-lasting prevention of relapse to cocaine seeking. However, mice relapsed when counterconditioned without, before, or long after memory retrieval, or when receiving LiCl without place counterconditioning. Our findings suggest that post-retrieval aversive counterconditioning leads to relapse prevention, possibly by replacing the cue-drug with a cue-aversion memory, thereby the cue ceases to evoke craving. Moreover, we found that a similar memory replacement procedure prevented relapse of conditioned place aversion. Hence, this novel procedure can also prevent relapse of aversive memories, providing a safe approach to alter various maladaptive behaviors.