Calciolangbeinite, ideally K2Ca2(SO4)3, exists in two modifications, cubic and, first described in the present paper, orthorhombic. They are topologically-similar polymorphs which can be designated as calciolangbeinite-C and calciolangbeinite-O. Calciolangbeinite-O is the first natural orthorhombic langbeinite-like sulfate. It clearly differs from calciolangbeinite-C in the powder X-ray diffraction pattern, optical data and Raman spectrum. Calciolangbeinite-O is found in sublimates of the active Arsenatnaya fumarole at the Tolbachik volcano, Kamchatka, Far Eastern Region, Russia and in pyrometamorphic rocks of the Hatrurim Complex at Jabel Harmun, Judean Desert, Palestinian Autonomy and Har Parsa, Negev Desert, both in Israel. Calciolangbeinite-C is known only in fumarole sublimates at Tolbachik. Calciolangbeinite forms a continuous solid-solution system with langbeinite K2Mg2(SO4)3. The majority of the system is represented by cubic phases, and only members with compositions K2(Ca2.0–1.9Mg0.0–0.1)(SO4)3 have orthorhombic symmetry under room-temperature conditions. The crystal structure of calciolangbeinite-O was studied on a single crystal, chemically very close to K2Ca2(SO4)3, from Tolbachik (R1 = 2.75%). The unit-cell parameters are: a = 10.3330(2), b = 10.5027(2), c = 10.1763(2) Å, V = 1104.37(4) Å3 and Z = 4; space group is P212121. Calciolangbeinite-O is a low-temperature modification of K2Ca2(SO4)3 belonging to the K2Cd2(SO4)3 structure type whereas calciolangbeinite-C (space group P213), a high-temperature modification, has the langbeinite-type structure. The significant Mg admixture in calciolangbeinite-C from Tolbachik probably stabilises its cubic structure at room temperature. In both high-temperature fumaroles and pyrometamorphic rocks calciolangbeinite crystallises in the cubic modification, and during cooling its chemical variety close to the end-member K2Ca2(SO4)3 undergoes phase transition to calciolangbeinite-O, whereas the Mg-enriched varieties of the mineral remain calciolangbeinite-C.