Low energy mechanical attrition under liquid nitrogen (i.e., cryomilling) was used to produce nanocrystalline Al-Mg alloy powders. The microstructural evolution during cryomilling of spray-atomized Al-7.5Mg (wt.%) alloy powders was characterized by using X-ray diffractometry and scanning electron microscopy. Cryomilling reduced the grain size to similar to 20 rim and produced a supersaturated face-centered cubic (fcc) solid solution having approximately 7.5 wt.% Mg in solution. The formation of nanocrystalline microstructure in the Al-Mg samples was associated with the total lattice strain of fcc Al, resembling that of other conventional milling processes with high or low milling energy levels. The nanocrystalline Al-Mg alloy powders were found to exhibit a high degree of thermal stability at elevated temperatures.