The identification of alternatives to the Lithium-ion battery architecture remains a crucial priority in the diversification of energy storage technologies. Accompanied by the low reduction potential of Ca2+/Ca, –2.87 V vs. SHE, metal-anode-based rechargeable Calcium (Ca) batteries appear competitive in terms of energy densities. However, the development of Ca-batteries lacks high-energy density intercalation cathode materials. Using first-principles methodologies, we screen a large chemical space for potential Ca-based cathode chemistries, with composition of CaiTMjZk, where TM is a 1st or 2nd row transition metal and Z is oxygen, sulfur, selenium or tellurium. 10 materials are selected and their Ca intercalation properties are investigated. We identify two previ- ously unreported promising electrode compositions: the post-spinel CaV2O4 and the layered CaNb2O4, with Ca migration barriers of ~654 meV and ~785 meV, respectively. Finally, we analyse the geometrical features of the Ca migration pathways across the 10 materials studied and provide an updated set of design rules for the identification of good ionic conductors, especially with large mobile cations.