We report the electrochemical performance of nanostructures of NaVO as cathode material for rechargeable batteries. The Rietveld refinement of room-temperature X-ray diffraction pattern shows the monoclinic phase with 2/ space group. The cyclic voltammetry curves of prepared half-cells exhibit redox peaks at 3.1 and 2.6 V, which are due to two-phase transition reaction between V and can be assigned to the single-step deintercalation/intercalation of Na ion. We observe a good cycling stability with specific discharge capacity (measured vs Na/Na) between 80 (±2) and 30 (±2) mAh g at current densities of 3 and 50 mA g, respectively. The electrochemical performance of NaVO electrode was also tested with Li anode, which showed higher capacity but decayed faster than Na. Using density functional theory, we calculate the Na vacancy formation energies: 3.37 eV in the bulk of the material and 2.52 eV on the (100) surface, which underlines the importance of nanostructures.