We combine experimentally verified constraints on brine thermodynamics along with a global circulation model to develop a new extensive framework of brine stability on the surface and subsurface of Mars. Our work considers all major phase changes (i.e., evaporation, freezing, and boiling) and is consistent, regardless of brine composition, so it is applicable to any brine relevant to Mars. We find that equatorial regions typically have temperatures too high for stable brines, while high latitudes are susceptible to permanent freezing. In the subsurface, this trend is reversed, and equatorial regions are more favorable to brine stability, but only for the lowest water activities (and lowest eutectic temperatures). At locations where brines may be stable, we find that their lifetimes can be characterized by two regimes. Above a water activity of ∼0.6, brine duration is dominated by evaporation, lasting at most a few minutes per sol. Below a water activity of 0.6, brine duration is bound by freezing or boiling; such brines are potentially stable for up to several consecutive hours per sol. Our work suggests that brines should not be expected near or on the Martian surface, except for low eutectic water activity salts such as calcium or magnesium perchlorate or chlorate, and their (meta)stability on the surface would require contact with atmospheric water vapor or local ice deposits.