Phase-change materials are of tremendous technological importance ranging from optical data storage to electronic memories. Despite this interest, many fundamental properties of phase-change materials, such as the role of vacancies, remain poorly understood. 'GeSbTe'- based phase-change materials contain vacancy concentrations around 10% in their metastable crystalline structure. By using density-functional theory, the origin of these vacancies has been clarified and we show that the most stable crystalline phases with rocksalt-like structures are characterized by large vacancy concentrations and local distortions. The ease by which vacancies are formed is explained by the need to annihilate energetically unfavourable antibonding Ge-Te and Sb-Te interactions in the highest occupied bands. Understanding how the interplay between vacancies and local distortions lowers the total energy helps to design novel phase-change materials as evidenced by new experimental data.