The Permian Haselgebirge Formation of the eastern Alps is among the most highly deformed evaporites worldwide. In underground salt mines, it is composed of a mélange of halite, anhydrite, and mudstone, with a subordinate amount of magmatic rocks. The only potassium mineral is polyhalite [K2Ca2Mg(SO4)4·2H2O]. Its extreme tectonic deformation provides a challenge for reconstructing the tectono-sedimentary environment. In this context, we were able to compile a set of characteristic sedimentary and early diagenetic features of the nonhalite components. In particular, mudstone and anhydrite pseudomorphs after gypsum preserve synsedimentary structures. While mudstone represents the overall background sedimentation, sulfate precipitated mainly at the brine surface under pelagic conditions. The large amount of mudstone (50%) was probably trapped as mud in a quiet lagoonal basin. Its magnesium-dominated mineral composition is in accordance with coeval halite precipitation from seawater. Earthquake-induced deformation structures formed in the semiductile mud sediment as mostly ramified, centimeter-scale sedimentary dikes, which originated intrastratally by liquefaction. Permian volcanism is documented by a basaltic body from the Hallstatt salt mine, which exhibits a sedimentary contact with the mudstone. Its immobile trace-element composition favors an intraplate origin consistent with a rift stage. During subsequent burial, authigenic minerals such as quartz and feldspar started to grow. The origin of polyhalite relates to the mobilization of complex fluids and roughly coincides with the final, late Middle Triassic opening of the Meliata Ocean. All evidence from synsedimentary deformation and early diagenesis confirms the deposition of the evaporites in a late thinning stage of an ancient rift.