Vanadyl phosphates (VOPO4) represent a class of attractive cathodes in lithium-ion batteries. However, the exploration of this type of materials in sodium-ion batteries is rare. Here, we report for the first time the synthesis of orthorhombic beta-NaVOPO4 by first chemically extracting lithium from beta-LiVOPO4 and then inserting sodium into the obtained beta-VOPO4 by a microwave-assisted solvothermal process with NaI, which serves both as a reducing agent and sodium source. Intermediate NaxVOPO4 compositions with x = 0.3, 0.5, and 0.8 have also been obtained by controlling the amount of NaI in the reaction mixture. Joint Rietveld refinement of synchrotron X-ray diffraction (XRD) and neutron diffraction confirms that the fully sodiated beta-NaVOPO4 is isostructural with the lithium counterpart beta-LiVOPO4. Bond valence sum maps suggest that sodium ions possibly diffuse along the [010] direction in the lattice, similar to the ionic conduction pathway in beta-LiVOPO4. Although the initial discharge capacity is low due to the protons in the structure, it steadily increases with cycling with a long plateau at 3.3 V. Ex situ XRD data of cycled beta-VOPO4 and beta-NaVOPO4 electrodes confirm the reversible reaction in sodium cells involving the V4+/V5+ redox couple.