The nanoscale order in amorphous GeTe thin films is measured using fluctuation transmission electron microscopy (FTEM). The order increases upon annealing at 145°C, which indicates a coarsening of subcritical nuclei. This correlates with a reduction in the nucleation delay time in laser crystallization. A shift in the FTEM peak positions may indicate a transformation in local bonding. In samples alloyed with 12 at. % nitrogen, the order does not change upon annealing, the peak does not shift, and the nucleation time is longer. The FTEM data indicate that nitrogen suppresses the structural evolution necessary for the nucleation process and increases the thermal stability of the material.