Today phase change memory (PCM) technology has reached product maturity at 90 and 65 nm nodes, while the 45 nm node is under development and is expected to enter in the market soon. The continuous decrease of the cell size with scaling leads to an effective active area as small as 150 nm(2) and an active volume involved in the phase transformation of about 10(4) nm(3), thus entering definitively into the nanotechnology world. At this extremely reduced dimension, the reliability of the device must be carefully investigated. In this work we show that the cycling performance of the device is well maintained, not being a problem for either the bipolar transistor or the storage element. The phase transition from the amorphous to the crystalline state is, of course, one of the most interesting phenomena, impacting cell retention capability and device performance. The stochastic nature of nano-nuclei percolation in the amorphous matrix is shown as an important ingredient in the retention of PCM devices. The related dispersion in crystallization times is analyzed through a crystallization Monte Carlo model and a physical insight into nucleation and growth mechanisms is provided.