We study memories capable of storing multiple bits per memory cell, with the property that certain state transitions "wear" the cell. We introduce a model that is relevant for Phase Change Memory, a promising emerging nonvolatile memory technology that exhibits limitations in the number of particular write actions that one may apply to a cell before rendering it unusable. We exploit the theory of Write Efficient Memories to derive a closed form expression for the storage capacity/lifetime fundamental tradeoff for this model. We then present families of codes specialized to distinct ranges for the target lifetimes, covering the full range from moderate redundancy to an arbitrarily large lifetime increase. These codes have low implementation complexity and remarkably good performance; for exam pIe in an 8 level cell we can increase the lifetime of a memory by a factor of ten while sacrificing only 2/3 of the uncoded storage capacity of the memory.© 2009 IEEE.