Sodium-selenium (Na-Se) batteries have aroused enormous attention due to the large abundance of the element sodium as well as the high electronic conductivity and volumetric capacity of selenium. In this battery system, some primary advances in electrode materials have been achieved, mainly involving the design of Se-based cathode materials. In this Review, the electrochemical mechanism is discussed, thus revealing the main challenges in Na-Se batteries. Then, the advances in the design of Se-based cathode materials for Na-ion storage are systemically summarized, classified, and discussed, including Se/carbon composite, Se/polar material/carbon composites, and hybrid SexSy alloys. Some potential strategies enabling the improvement of crucial challenges and enhancement of electrochemical performance are also proposed to provide guidelines for the enhancements of Na-ion storage. An outlook for future valuable research directions is proposed to understand more deeply the electrochemical mechanism of Na-Se batteries and promote their further developments in full cell performance and commercialization.