Phase-change materials (PCMs) are finding wide applications in emerging technologies such as nonvolatile phase-change random-access memory and in-memory computing devices by utilising the ultrafast and reversible amorphous-to-crystal transition. The crystallisation of the amorphous state is much slower compared to the crystal melting, hence representing a bottleneck in the further development of new technologies. Here, we disclose the detailed crystallisation pathway of amorphous Ge2Sb2Te5 (GST) via ab initio molecular dynamics simulations. By probing the local order with a highly sensitive metric, we detect the formation of a sub-critical nucleus formed by the spontaneous aggregation of highly ordered octahedral-like atoms. Specifically, we observe that Sb atoms recover octahedral-like geometry quicker than Ge atoms, implying that the different mobility of different species plays a central role in the overall process. With respect to other less locally-ordered (hence transient) domains, this stable precursor is characterised by lower energy, is resilient to melting, and acts as a skeleton over which the critical nucleus further develops. The detailed understanding of the kinetics of homogeneous nucleation in GST opens the doorway for the development of more efficient PCM-based storage devices by a rational composition design and, ultimately, for the boosting of the speed and efficiency of computing architectures.