Al-Mg alloys are normally prone to lose part of their yield and tensile strength at high temperatures due to insufficient thermal stability of the microstructure. Here, we present a Ca-modified Al–Mg–Sc alloy demonstrating high strength at elevated temperatures. The microstructure contains Al₄Ca phases distributed as a network along the grain boundary and Al₃(Sc,Zr) nano-particles dispersed within the grains. The microstructure evolution and age-hardening analysis indicate that the combination of an Al₄Ca network and Sc-rich nano-particles leads to excellent thermal stability even upon aging at 300 °C. The tensile strength of the alloy for temperatures up to 250 °C is significantly improved by an aging treatment and is comparable with the commercial heat-resistant aluminum alloys, i.e., A356 and A319. At a high temperature of 300 °C, the tensile strength is superior to the above-mentioned commercial alloys, even more so when expressed as the specific strength due to the low density of Ca-modified Al–Mg–Sc alloy. The excellent high-temperature strength results from a synergistic effect of solid solution strengthening, grain boundary strengthening and nanoparticle order strengthening.