The crystallization rate is an important factor for the application of phase change materials as memory devices, which, thus, motivates a strong interest in the underlying crystallization processes. We analyzed the crystallization kinetics of as-deposited amorphous Ge2Sb2Te5 by differential scanning calorimetry, revealing that the thermal treatment below the crystallization onset temperature effectively enhances the crystallization rate compared to the as-deposited samples. Variable resolution fluctuation electron microscopy was carried out to characterize the corresponding amorphous structure of the as-deposited films and the differently annealed states regarding their medium-range order (MRO). As a result, relatively large MRO correlation lengths in the range of 3–4 nm were observed, whereas the MRO volume fraction doubled after longer annealing treatments, demonstrating the importance of MRO and MRO tuning for optimizing the properties of amorphous phase change materials. The increased volume fraction of the MRO seems to also favor an increased nanoindentation hardness.