The crystal structures of two new tetravalent terbium fluorides, CaTbF6 and CdTbF6, have been determined from X-ray and neutron powder diffraction data. The title compounds exhibit an anti-KSbF6 structure, the three-dimensional framework of which is built of [TbF6]2- chains of edge-sharing dodecahedra further linked, by sharing corners, to isolated [MF6]4- octahedra (M=Ca, Cd). The mechanism of the anionic sublattice rearrangement when going from KSbF6 to CaTbF6 is described and related to a simple cubic fluoride-ion packing. Comparison with the crystal structures of beta-BaTbF6 and other representatives of the M(II)M('IV)F6 family allows the singular crystal-chemical properties of some fluoroterbates to be emphasized.