Al-Mg alloys are a series of low cost and low density Al alloys, which show remarkable strengthening during deformation. In this work, study of commercial purity Al, Al-0.5Mg and Al-4.1Mg alloys was carried out to investigate the effect of Mg on materials strengthening. Slight solid solution strengthening by Mg addition is found in the as-cast alloys. While further significant strengthening effect is achieved in the alloys produced by high pressure torsion. An extraordinarily high strength of ~800 MPa is achieved in the Al-4.1Mg alloy, as a result of deformation induced ultrafine grains, high density stacking faults and Mg segregation.