Phase-change optical memories are based on the astonishingly rapid nanosecond-scale crystallization of nanosized amorphous ‘marks’ in a polycrystalline layer. Models of crystallization exist for the commercially used phase-change alloy Ge2Sb2Te5 (GST), but not for the equally important class of Sb–Te-based alloys. We have combined X-ray diffraction, extended X-ray absorption fine structure and hard X-ray photoelectron spectroscopy experiments with density functional simulations to determine the crystalline and amorphous structures of Ag3.5In3.8Sb75.0Te17.7 (AIST) and how they differ from GST. The structure of amorphous (a-) AIST shows a range of atomic ring sizes, whereas a-GST shows mainly small rings and cavities. The local environment of Sb in both forms of AIST is a distorted 3+3 octahedron. These structures suggest a bond-interchange model, where a sequence of small displacements of Sb atoms accompanied by interchanges of short and long bonds is the origin of the rapid crystallization of a-AIST. It differs profoundly from crystallization in a-GST.