Electrolyte selection for Plasma Electrolytic Oxidation (PEO) of magnesium is important as this determines composition, morphology and properties of resultant coatings that are urgently sought after for protection of Mg alloys from corrosion and wear in harsh environments. However, electrolyte design is often performed heuristically, which hampers the development and optimisation of new PEO processes. Here, we attempt to achieve a mechanistic understanding of electrochemical and microstructural aspects of anodic films evolution at the pre-breakdown stages of PEO treatments of magnesium in aqueous alkaline solutions of NaAlO₂, Na₃PO₄, NaF and Na₂SiO₃. Systematic studies have shown that magnesium self-passivation by MgO/Mg(OH)₂ can be compromised by both chemical and mechanical instabilities developed due to side effects of anodic reactions. Stable initiation of PEO process requires maintaining surface passivity in a wide range of pH, which can be achieved only by combining self-depositing passivators with those binding dissolved magnesium into insoluble compounds.