If Mars ever possessed a salty liquid hydrosphere, which later partly evaporated and froze down, then any aqueous fluids left near the surface could have evolved to become dense eutectic brines. Eutectic brines, by definition, are the last to freeze and the first to melt. If CaCl2-rich, such brines can remain liquid until temperatures below 220¿K, close to the average surface temperature of Mars. In the Martian subsurface, in intimate contact with the Ca-rich basaltic regolith, NaCl-rich early brines should have reacted to become Ca-rich. Fractional crystallization (freezing) and partial melting would also drive brines toward CaCl2-rich compositions. In other words, eutectic brine compositions could be present in the shallow subsurface of Mars, for the same reasons that eutectic magma compositions are common on Earth. Don Juan Pond, Antarctica, a CaCl2-rich eutectic brine, provides a possible terrestrial analog, particularly because it is fed from a basaltic aquifer. Owing to their relative density and fluid nature, brines in the Martian regolith should eventually become sandwiched between ice above and salts beneath. A thawing brine sandwich provides one explanation (among many) for the young gullies recently attributed to seepage of liquid water on Mars. Whether or not brine seepage explains the gullies phenomenon, dense, CaCl2-rich brines are to be expected in the deep subsurface of Mars, although they might be somewhat diluted (temperatures permitting) and of variable salt composition. In any case, they should be good conductors of electricity.