Ge-Sb-Te alloys have been widely used in optical/electrical memory storage. Because of the extremely fast crystalline-amorphous transition, they are also expected to play a vital role in next generation nonvolatile microelectronic memory devices. However, the distribution and structural properties of vacancies have been one of the key issues in determining the speed of melting (or amorphization), phase-stability, and heat-dissipation of rock-salt GeSbTe, which is crucial for its technological breakthrough in memory devices. Using spherical aberration-aberration corrected scanning transmission electron microscopy and atomic scale energy-dispersive X-ray mapping, we observe a new rock-salt structure with high-degree vacancy ordering (or layered-like ordering) at an elevated temperature, which is a result of phase transition from the rock-salt phase with randomly distributed vacancies. First-principles calculations reveal that the phase transition is an energetically favored process. Moreover, molecular dynamics studies suggest that the melting of the cubic rock-salt phases is initiated at the vacancies, which propagate to nearby regions. The observation of multi-rock-salt phases suggests another route for multi-level data storage using GeSbTe.