Divalent calcium ion conducting solid electrolyte with three-dimensional NASICON-type structure, (CaxHf1-x)(4/(4-2x))Nb(PO4)(3), was successfully developed by introducing Ca2+ cations into HfNb(PO4)(3) as mother solid. The existence of three kinds of high valence cation, Hf4+, Nb5+, and P5+, in the structure successfully realized the effective reduction of electrostatic interaction functioned to Ca2+ in the structure. The (Ca0.05Hf0.95)(4/3.9)Nb(PO4)(3) solid showed considerably higher Ca2+ cation conductivity and lower activation energy than those of previously reported NASICON-type Ca0.5Zr2(PO4)(3) solid.