Although Complex Metallic Alloy phases (CMAs) are known since the beginning of the last century, they have long been considered as rare and special cases of intermetallic compounds.Recent phase diagram studies using state of the art techniques have shown that CMAs occur frequently not only in multinary but also in binary systems.Hence it is important to understand how these structures of tremendous complexity are stabilized.Because phase diagram studies are tedious, expensive and time consuming, special attention has been paid during the last two decades primarily to Al and Mg based systems promising the design of advanced light metal intermetallics.The aim of this contribution is to present examples of recent studies of Mg-based phase diagrams containing large numbers of complex metallic alloy phases.The following topics will be addressed in more detail: i) The art of phase diagram determination, i.e., advanced preparation and characterisation techniques for complex phase diagrams; ii) How do we describe large unit cell structures with thousands of atoms?iii) Disorder phenomena and their role in structure stabilisation-enthalpy versus entropy; iv) What can we learn from calculations combined with data mining techniques and/or experimental data?We gratefully acknowledge the support of the European Network of Excellence Complex Metallic Alloys, Contract No. NMP3- CT-2005-500140.