Many features of the Martian landscape are thought to have been formed by liquid water flow and water-related mineralogies on the surface of Mars are widespread and abundant. Several lines of evidence, however, suggest that Mars has been cold with mean global temperatures well below the freezing point of pure water. Martian climate modellers considering a combination of greenhouse gases at a range of partial pressures find it challenging to simulate global mean Martian surface temperatures above 273 K, and local thermal sources cannot account for the widespread distribution of hydrated and evaporitic minerals throughout the Martian landscape. Solutes could depress the melting point of water in a frozen Martian environment, providing a plausible solution to the early Mars climate paradox. Here we model the freezing and evaporation processes of Martian fluids with a composition resulting from the weathering of basalts, as reflected in the chemical compositions at Mars landing sites. Our results show that a significant fraction of weathering fluids loaded with Si, Fe, S, Mg, Ca, Cl, Na, K and Al remain in the liquid state at temperatures well below 273 K. We tested our model by analysing the mineralogies yielded by the evolution of the solutions: the resulting mineral assemblages are analogous to those actually identified on the Martian surface. This stability against freezing of Martian fluids can explain saline liquid water activity on the surface of Mars at mean global temperatures well below 273 K.