Regarding safety, cost and volumetric capacity, magnesium batteries could be an alternative to lithium ones. However, it is needed to find more suitable electrode materials and electrolyte solutions for developing rechargeable magnesium batteries. In this work, nanobelts of sodium vanadate (NVO) have been prepared and evaluated as electrode material in magnesium battery. Intercalation of magnesium and sodium into NVO has been explored using first-principles calculations. The experimental intercalation of magnesium was studied using both wet and dry electrolyte solutions based on different organic solvents. It is found that the electrochemical behavior strongly depends on the electrolyte solution, and the maximum reversible capacity is around 200–270 mAh g⁻¹ using wet electrolyte. The mechanism of the electrochemical reaction has been studied by using XRD and chemical microanalysis. During the discharge/charge process, magnesium ions are reversibly intercalated/deintercalated, while sodium ions remain in the framework of NVO. The results make sodium vanadate an attractive candidate for an electrode in magnesium batteries.