Background and aims Aluminum (Al) toxicity and magnesium (Mg) deficiency often coexist in acidic soils. Nitric oxide (NO) is involved in diverse physiological processes and stress responses. Here, we investigated the role of NO in Mg-mediated root growth promotion and Al tolerance in Arabidopsis. Methods Physiological and pharmacological methods together with molecular and genetic analyses were used. Results Al toxicity- and Mg deficiency-induced NO production contributed to inhibition of primary root growth. In contrast, Mg supply promoted root growth associated with decreasing NO production under Al stress and/or Mg deficiency conditions. Magnesium decreased the activities and expression of the genes related to NO biosynthesis enzymes in Col-0 roots. The NO-associated protein 1 mutant noa1 and the nitrate reductase mutant nia1nia2 with impaired NO production showed Al toxicity- and Mg deficiency-insensitive phenotypes, further confirming involvement of NO in Mg-mediated root growth promotion and alleviation of Al toxicity. Conclusions Taken together, our results suggested that Mg-mediated enhancement of root growth and Al tolerance is associated with altering NO production in Arabidopsis.