The Messinian salinity crisis (MSC) is perceived as an environmental crisis governed by climatic and tectonic controls, affecting global oceans’ salinity and shaping the Mediterranean Sea’s biochemical composition. Recently drilled offshore wells in the Levant Basin retrieved a sedimentary record of the deep-basin Mediterranean MSC salt deposits and the underlying pre-evaporite unit. In this study, we have concentrated on the pre-evaporite interval and its transition into the overlying evaporites. Analysis of this data set changes the way these deposits have been perceived since the 1970s, when they were first penetrated in their uppermost part during Deep Sea Drilling Project expeditions. Using sedimentology, seismic interpretation, biostratigraphy, and astronomical tuning, we show that Messinian salt deposition in the Eastern Mediterranean began during stage 1 of the MSC. In contrast to the present paradigm, salt was deposited synchronously with gypsum in the marginal and intermediate-depth basins significantly before the 50 k.y. interval coined as the “MSC acme event”, ∼400 k.y. after the crisis began. Thus salt precipitation took place in a non-desiccated deep basin, having a restricted but often open connection with the Atlantic Ocean, substantially altering our understanding of the mechanisms governing the deposition of salt giants. A coeval onset of basinal halite and marginal gypsum precipitation calls for a revaluation of global-scale climatic and oceanographic models of the MSC, taking into account a much older age for the beginning of halite deposition.