Rechargeable Mg batteries are promising candidates for highly safe large-scale energy storage batteries owing to their low-cost and non-dendritic metallic Mg anode. However, exploration of high-performance cathodes remains a great challenge hindering their development. Herein, a new pseudocapacitive Mg-storage nanowire material (a-MoS3@CNT) is constructed with a carbon nanotube (CNT) core and an amorphous MoS3 (a-MoS3) outer layer (15 nm thick). The nanowire cathode exhibits a high reversible capacity of 175 mA h g-1 at 100 mA g-1, a good rate performance of 50 mA h g-1 at 1000 mA g-1, and an outstanding long-term cyclability over 500 cycles. Further investigation of the mechanism demonstrates that the Mg-storage of a-MoS3@CNT is mainly achieved by the pseudocapacitance of a-MoS3, in which Mg2+ ions show fast solid-state diffusion kinetics. The present results demonstrate a new approach for efficient Mg-storage using pseudocapacitive materials, and the performance and solid-state Mg2+ diffusion kinetics could be optimized by delicate morphology tailoring.