Exploring the redistribution mechanism of Mg from the perspective of experimental observation has been a long-term yet challenging attempt in Al-Mg alloys. Here we demonstrate a simple but effective approach to obtain non-uniform Mg solute distribution (i.e., Mg-enriched/depletion zones) around typical grain boundaries (GBs) in a nanocrystalline Al-8 Mg alloy. This abnormal segregation was detected by both high-angle annular dark-field scanning transmission electron microscopy and atom probe tomography. The results show that local strain and GB migration during deformation leads to spatially inhomogeneous Mg solute distribution around the GBs. Both the non-uniform distribution and the broadened GBs can hinder GB migration and dislocation motion, thus enhance the strength. An inhomogeneous solute distribution mechanism of Mg atoms is proposed based on the extensive investigations. This study may help with developing new strengthening mechanisms of nanocrystalline materials