Mg batteries utilizing a Mg metal anode with a high-voltage intercalation cathode define a potential pathway toward energy storage with high energy density. However, the making of Mg batteries is plagued by the instability of existing electrolytes against the Mg-metal anode and high-voltage cathode materials. One viable solution to this problem is the identification of protective coating materials that could effectively separate the distinct chemistries of the metal-anode and the cathode materials from the electrolyte. Using first-principles calculations we mapped the electrochemical stability windows for non-redox-active Mg binary and ternary compounds in order to identify potential coating materials for Mg batteries. Our results identify Mg-halides and Mg(BH4)2 as promising anode coating materials based on their significant reductive stability. On the cathode side, we single out MgF2, Mg(PO3)2, and MgP4O11 as effective passivating agents.