The mineral eldfellite, NaFe(SO4)2, was recently proposed as an inexpensive candidate for the next generation of cathode application in Na-based batteries. Employing the density functional theory framework, we have investigated the phase stability, electrochemical properties and ionic diffusion of this eldfellite cathode material. We showed that the crystal structure undergoes a volume shrinkage of ≈8% upon full removal of Na ions with no imaginary frequencies at the Γ point of phonon dispersion. This evokes the stability of the host structure. According to this result, we proposed structural changes to get higher specific energy by inserting two Na ions per redox-active metal. Our calculations indicate NaV(SO4)2 as the best candidate with the capability of reversibly inserting two Na ions per redox center and producing an excellent specific energy. The main bottleneck for the application of eldfellite as a cathode is the high activation energies for the Na+ ion hop, which can reach values even higher than 1 eV for the charged state. This effect produces a low ionic insertion rate.