Methods of programming a phase-change memory device that remedy device failure. The methods includes applying a sequence of two or more electrical energy pulses to the device, where the sequence of pulses includes positive polarity pulses and negative polarity pulses. In one method, two or more pulses of an initial polarity are applied and are followed by one or more pulses having opposite polarity. In another method, pulses of an initial polarity are repeatedly applied until the device fails and one or more pulses of opposite polarity are subsequently applied to restore the device to its initial performance. The pulses may be set pulses, reset pulses, or pulses that produce programmed states having a resistance intermediate between the set resistance and reset resistance of the device.