Using laser-heated diamond-anvil cells, we have observed CaSO4 undergoing phase transitions from its ambient anhydrite structure to the monazite type, and at highest pressure and temperature to crystallize in the barite-type structure. On cooling, the barite structure distorts from an orthorhombic to a monoclinic lattice to produce the AgMnO4-type structure. The barite-structured form of CaSO4 that we encounter at high pressure and temperature has been, in particular, long expected as a high- pressure phase of CaSO4-anhydrite from systematic trends of similar AIIBVIO4-type sulfates, selenates, and tellurates, but has not been observed before. Similarly, the monoclinic distortion of the barite structure has itself been proposed as an intermediate phase between anhydrite and barite types through comparison with the phase diagrams of NaBF4 and NaClO4. This result has important consequences for identifying structural trends between different ABO4-type phases of Group II sulfates, selenates, tellurates, chromates, molybdates and tungstates that crystallize in anhydrite, zircon, monazite, barite and scheelite-type structures at ambient and high pressures.