The influences of the chemical composition and the heat-treatment conditions on both the crystallisation behaviour and the high-temperature stability (HTS) of three types of amorphous stone wool fibres of iron-bearing alumino-silicate composition are studied by performing thermal, structural, and compositional analyses. The fibres heat-treated under oxidising conditions exhibit outstanding HTS, i.e., the fibres are able to maintain their original geometric shape in a high-temperature environment. This is attributed to the formation of a nano-crystalline layer on the surface of the fibres as a consequence of the oxidation of Fe2+ to Fe3+. The layer remains after the bulk crystallisation process has been completed. The thickness of the layer increases with increasing initial content of Fe2+ and Mg2+ in the fibres. The nanolayer influences the bulk crystallisation in the manner that it lowers the crystallisation onset temperature, the activation energy, and the Avrami parameter. Such influence benefits the enhancement of the HTS. In contrast, the fibres heat-treated under reducing and inert conditions exhibit poor HTS. This is attributed to the early viscous heating of the fibres because of lack of the nano-crystalline surface layer. The HTS does not depend on the identity of the bulk crystalline phases.