Phase-change memory (PCM) has emerged as one among the most promising technologies for next-generation nonvolatile solid-state memory. Multilevel storage, namely storage of non-binary information in a memory cell, is a key factor for reducing the total cost-per-bit and thus increasing the competitiveness of PCM technology in the nonvolatile memory market. In this paper, we present a family of advanced programming schemes for multilevel storage in PCM. The proposed schemes are based on iterative write-and-verify algorithms that exploit the unique programming characteristics of PCM in order to achieve significant improvements in resistance-level packing density, robustness to cell variability, programming latency, energy-per-bit and cell storage capacity. Experimental results from PCM test-arrays are presented to validate the proposed programming schemes. In addition, the reliability issues of multilevel PCM in terms of resistance drift and read noise are discussed. © 2011 IEEE.