Chalcogenide-based phase change materials (PCMs) are promising candidates for the active element in novel electrical nonvolatile memories and have been applied successfully in rewritable optical disks. Nanostructured PCMs are considered as the next generation building blocks for their low power consumption, high storage density, and fast switching speed. Yet their crystallization kinetics at high temperature, the rate-limiting property upon switching, faces great challenges due to the short time and length scales involved. Here we present a facile method to synthesize highly controlled, ligand-free GeTe nanoparticles, an important PCM, with an average diameter under 10 nm. Subsequent crystallization by slow and ultrafast rates allows unravelling of the crystallization kinetics, demonstrating the breakdown of Arrhenius behavior for the crystallization rate and a fragile-to-strong transition in the viscosity as well as the overall crystal growth rate for the as-deposited GeTe nanoparticles. The obtained results pave the way for further development of phase-change memory based on GeTe with sub-lithographic sizes.