The development of energy storage technologies that are alternative to state-of-the-art lithium-ion batteries but exhibit similar energy densities, lower cost, and better safety is an important step in ensuring a sustainable energy future. Electrochemical systems based on calcium (Ca)-intercalation or deintercalation form such an alternative energy storage technology but require the development of intercalation electrode materials that exhibit reversible Ca-exchange with reasonable energy density and power density performance. To address this issue, we use first-principles calculations to screen over the wide chemical space of sodium superionic conductor (NaSICON) frameworks, with a chemical formula of CaxM2(ZO4)3 (where M = Ti, V, Cr, Mn, Fe, Co, or Ni and Z = Si, P, or S) for Ca electrode materials. We calculate the average Ca2+ intercalation voltage, the thermodynamic stability (at 0 K) of charged and discharged Ca-NaSICON, and the migration barriers of (meta)stable Ca-NaSICON compositions. Importantly, our calculations indicate CaxV2(PO4)3, CaxMn2(SO4)3, and CaxFe2(SO4)3 Ca-NaSICONs to be promising as Ca-cathodes. We find all silicate Ca-NaSICONs to be thermodynamically unstable and hence unsuitable as Ca-cathodes. We report the overall trends in the ground state Ca-vacancy configurations, besides voltages, stabilities, and migration barriers. Our work contributes to unearthing strategies for developing practical calcium-ion batteries, involving polyanionic intercalation frameworks.