Natural abundance of sodium and its similar behavior to lithium triggered recent extensive studies of cost-effective sodium-ion batteries (SIBs) for large-scale energy storage systems. A challenge is to develop electrode materials with a high electrode potential, specific capacity and a good rate capability. In this work we propose mixed eldfellite compounds Na-5(Fe1/2M1/2)(SO4)(2) (x = 0-2, M = Mn, Co, Ni) as a new family of high electrode potential cathodes of SIBs and present their material properties predicted by first-principles calculations. The structural optimizations show that these materials have significantly small volume expansion rates below 5% upon Na insertion/desertion with negative Na binding energies. Through the electronic structure calculations, we find band insulating properties and hole (and/or electron) polaron hoping as a possible mechanism for the charge transfer. Especially we confirm the high electrode voltages over 4 V with reasonably high specific capacities. We also investigate the sodium ion mobility by estimating plausible diffusion pathways and calculating the corresponding activation barriers, demonstrating the reasonably fast migrations of sodium ions during the operation. Our calculation results indicate that these mixed eldfellite compounds can be suitable materials for high performance SIB cathodes.