Single crystals of two new calcium perrhenates, anhydrous Ca(ReO4)2 (1) and K2Ca3(ReO4)8·4H2O (2), were prepared during solid-state and solution attempts to prepare the potassium analog of NaCa(ReO4)3. Both structures can be regarded as frameworks comprised of vertex-sharing CaO8 and ReO4 polyhedra. 1 is a complete structural analog of Sr(ReO4)2 while 2 corresponds to its own structure type. It is also the first hydrated binary perrhenate to date. We discuss the similarities and differences in the structures of alkaline earth perrhenates and pertechnetates; existence of more complex and elegant metal-perrhenate architectures is predicted.