Liquid water on Mars might be created by deliquescence of hygroscopic salts or by permafrost melts, both potentially forming saturated brines. Freezing point depression allows these heavy brines to remain liquid in the near-surface environment for extended periods, perhaps as eutectic solutions, at the lowest temperatures and highest salt concentrations where ices and precipitates do not form. Perchlorate and chlorate salts and iron sulphate form brines with low eutectic temperatures and may persist under Mars near-surface conditions, but are chemically harsh at high concentrations and were expected to be incompatible with life, while brines of common sulphate salts on Mars may be more suitable for microbial growth. Microbial growth in saturated brines also may be relevant beyond Mars, to the oceans of Ceres, Enceladus, Europa and Pluto. We have previously shown strong growth of salinotolerant bacteria in media containing 2M MgSO4 heptahydrate (∼50% w/v) at 25°C. Here we extend those observations to bacterial isolates from Basque Lake, BC and Hot Lake, WA, that grow well in saturated MgSO4 medium (67%) at 25°C and in 50% MgSO4 medium at 4°C (56% would be saturated). Psychrotolerant, salinotolerant microbes isolated from Basque Lake soils included Halomonas and Marinococcus, which were identified by 16S rRNA gene sequencing and characterized phenetically. Eutectic liquid medium constituted by 43% MgSO4 at '4°C supported copious growth of these psychrotolerant Halomonas isolates, among others. Bacterial isolates also grew well at the eutectic for K chlorate (3% at '3°C). Survival and growth in eutectic solutions increases the possibility that microbes contaminating spacecraft pose a contamination risk to Mars. The cold brines of sulphate and (per)chlorate salts that may form at times on Mars through deliquescence or permafrost melt have now been demonstrated to be suitable microbial habitats, should appropriate nutrients be available and dormant cells become vegetative.