In search of high energy density cathode materials, the eldfellite mineral-type NaVIII(SO4)2 compound has been theoretically predicted to be a promising cathode insertion host for sodium-ion batteries. Synergizing computational and experimental investigations, the current work introduces NaVIII(SO4)2 as a novel versatile cathode for Li-ion and Na-ion batteries. Prepared by a low temperature sol-gel synthesis route, the eldfellite NaV(SO4)2 cathode exhibited an initial capacity approaching ∼79% (vs. Li+/Li) and ∼69% (vs. Na+/Na) of the theoretical capacity (1e− ≅ 101 mA h g−1) involving the V3+/V2+ redox potential centered at 2.57 V and 2.28 V, respectively. The bond valence site energy (BVSE) approach and DFT-based calculations were used to gain mechanistic insight into alkali ion migration and probe the redox center during (de)insertion of Li+/Na+ ions. Post-mortem and electrochemical titration tools revealed the occurrence of a single-phase (solid-solution) redox mechanism during reversible Li+/Na+ (de)insertion into NaVIII(SO4)2. With the multivalent vanadium redox center, eldfellite NaVIII(SO4)2 forms a new cathode insertion host for Li/Na-ion batteries with potential two-electron uptake.