The new compounds NaMV2(PO4)3 (M = Fe, Co, Ni) were synthesized via a sol-gel synthesis route, and their crystal structures were refined using the Rietveld method from X-ray powder diffraction data. NaCoV2(PO4)3 was also characterized by TGA, cyclic voltammetry, and galvanostatic cycling. The three phases crystallize with the orthorhombic symmetry and the space group Imma. The structures are isotypic to the stuffed α-CrPO4-type structure and contain two vacant sites in which two sodium atoms can be intercalated. When NaCoV2(PO4)3 is cycled at a 1C rate in the voltage ranges of 0.1-3 and 0.7-3 V vs Na+/Na, it delivers specific capacities of 190 and 75 mA h/g, respectively, with an average operation potential of ∼1.4 V. This attests to the electrochemical activity of this compound and indicates that the α-CrPO4-type compounds could be suitable for hosting other guest ions.