The effects of multi-walled carbon nano-tubes (MWCNTs) and the ball milling parameters on the mechanical properties of the Al-Mg alloy powders were investigated. Three different composite powders were synthesized through ball-milling process at different time and milling rates. The microstructural and phase analyses were carried out via scanning electron microscopy and X-ray diffraction spectroscopy, respectively. The results indicated that increasing the ball-milling time and rate would lead to the formation of finer particles, which consequently intensifies the plastic deformation and then, results in lower crystallite size. The morphological investigations indicated that while the MWCNTs agglomerates in lower milling rates, increased milling rate not only improve the distribution of the MWCNTs, but also decreases the length of the nano-tubes and promotes their diffusion into Al-Mg matrix. The formation of Al-Mg intermetallic phases through the ball-milling process of the composite powders was also confirmed via microstructural investigations.