A method for programming multilevel PCM cells envisages: forming an amorphous region of amorphous phase change material in a storage element of a PCM cell by applying one or more reset pulse; and forming a conductive path of crystalline phase change material through the amorphous region by applying one or more set pulse, a size of the conductive path defining a programmed state of the PCM cell and an output electrical quantity associated thereto, and being controlled by the value of the reset pulse and set pulse. The step of forming an amorphous region envisages adaptively and iteratively determining, during the programming operations, a value of the reset pulse optimized for electrical and/or physical properties of the PCM cell, and in particular determining a minimum amplitude value of the reset pulse, which allows programming a desired programmed state and a desired value of the output electrical quantity.