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 standard hydrogen electrode, 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 first- or second-row transition metal and Z is oxygen, sulfur, selenium, or tellurium. Ten materials are selected, and their Ca intercalation properties are investigated. We identify two previously unreported promising electrode compositions: the post-spinel CaV2O4 and the layered CaNb2O4, with Ca migration barriers of ∼654 and ∼785 meV, respectively. We analyze 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.