Chalcogenide-based nanostructured phase-change materials (PCMs) are considered promising building blocks for non-volatile memory due to their high write and read speeds, high data-storage density, and low power consumption. Top-down fabrication of PCM nanoparticles (NPs), however, often results in damage and deterioration of their useful properties. Gas-phase condensation based on magnetron sputtering offers an attractive and straightforward solution to continuously down-scale the PCMs into sub-lithographic sizes. Here we unprecedentedly present the size dependence of crystallization for Ge2Sb2Te5 (GST) NPs, whose production is currently highly challenging for chemical synthesis or top-down fabrication. Both amorphous and crystalline NPs have been produced with excellent size and composition control with average diameters varying between 8 and 17 nm. The size-dependent crystallization of these NPs was carefully analyzed through in-situ heating in a transmission electron microscope, where the crystallization temperatures (Tc) decrease when the NPs become smaller. Moreover, methane incorporation has been observed as an effective method to enhance the amorphous phase stability of the NPs. This work therefore elucidates that GST NPs synthesized by gas-phase condensation with tailored properties are promising alternatives in designing phase-change memories constrained by optical lithography limitations.