New aluminum alloys, based on a commercial Al-Mn-Cu brazing sheet core alloy, with increasing alloying element Mg up to 2 wt.%, have been developed for automotive heat exchanger units in service at above 200°C. The new Al-Mn-Cu-Mg alloys are to be used as the core material in brazing sheets for vacuum and nickel brazing technologies. They were DC cast to 3.75″ lab sized ingots, scalped, re-heated to 520°C, hot rolled to 4.8 - 5mm, and cold rolled down to a final gauge of 1mm. It has been demonstrated by various mechanical and corrosion testing that Mg contributes a strong solid solution hardening effect at both the room and elevated temperatures, without damaging the other mechanical properties or corrosion resistance. Hence the alloys with 1 - 2 wt.% Mg are able to maintain high yield strength above 60 MPa at 200 - 300°C, with no reduction in formability and very limited decrease in corrosion resistance. Since the new alloys do not contain expensive alloying elements, there is no significant increase in material or processing costs.