The energy storage system utilizing calcium as a charge carrier is gaining prominence due to its abundance in the Earth’s crust, reduction potential that is comparable to lithium (Li/Li+=−3.04V, Ca/Ca2+=−2.84V), and its nontoxic nature. Enabling practical Ca-ion batteries demands overcoming challenges in forming both electrically nonconductive and ionically conductive SEI layers. We propose a coating strategy and thermodynamic screening via the Materials Project database to pinpoint suitable coating materials. Our selection criteria encompass phase stability, electronic properties, and electrochemical stability. Among 787 compounds, we identified 46 candidates (29 anodic, 24 cathodic, and 7 of them are on both sides) based on reduction/oxidation potential and width of the stability window. Optimal compounds such as Ca4Cl6O and CaCN2 for anodes, and Ca(AlCl4)2, CaCO3, CaSO4, KCaF3, and CaAlF5 for cathodes exhibit superior interfacial stability for electrode coating, holding promise for Ca-ion batteries. This study can provide foundational insights into coating materials for Ca-ion batteries, offering guidance for electrode interface stabilization and practical battery design.