Despite the application of treatments that combine methadone administration, weekly counseling, and contingency reinforcement strategies, many opiate-dependent patients continue illicit drug use. In this controlled study we piloted a novel cognitive-behavioral treatment (CBT) designed to reduce illicit drug use among patients receiving methadone treatment. The treatment targeted the reduction of sensitivity to interoceptive cues associated with drug craving, and trained alternative responses to these cues. Patients (N = 23) were randomly assigned to either this novel CBT program or a program of increased counseling, such that the two programs of treatment were equated for therapist contact, assessment time, and contingency-reinforcement strategies. We found that, compared to a doubling of contact with their outpatient counselor, the new program was associated with significantly greater reductions in illicit drug use for women, but not for men. Reasons for differential performance by women and men and future directions for this new treatment are discussed.