A stochastic cellular automata simulator capable of spatiotemporal modeling of the crystallization and amorphization behavior of phase-change materials during the complex annealing cycles used in optical and electrical memory applications is presented. This is based on consideration of bulk and surface energies to generate rates of growth and decay of crystallites built up from “monomers” that may themselves be quite complex molecules. The approach uses a stochastic Gillespie-type time-stepping algorithm to deal with events that may occur on a very wide range of time scales. The simulations are performed at molecular length scale and using an approximation of local free energy changes that depend only on immediate neighbors. The approach is potentially capable of spanning the length scales between ab initio atomistic modeling methods, such as density functional theory, and bulk-scale methods, such the Johnshon–Mehl–Avrami–Kolmogorov formalism. As an example the model is used to predict the crystallization behavior in the chalcogenide Ge2Sb2Te5 alloy commonly used in phase-change memory devices. The simulations include annealing cycles with nontrivial spatial and temporal variations in temperature, with good agreement to experimental incubation times at low temperatures while modeling nontrivial crystal size distributions and melting dynamics at higher temperatures.