Rechargeable Mg batteries are promising candidates for highly safe, large-scale energy storage batteries due to the low-cost and non-dendritic metallic Mg anode. However, exploring high-performance cathodes remains a great challenge blocking their development. Herein, a rechargeable Mg battery is established with a Ag2S conversion cathode, providing a highly reversible capacity of 120 mA h g-1 at 50 mA g-1, a superior rate capability of 70 mA h g-1 at 500 mA g-1, and an outstanding long-term cyclability over 400 cycles. The mechanism was investigated using XRD, TEM and XPS in addition to electrochemical measurements, and indicated a two-stage magnesiation: first, Mg2+ intercalation into Ag2S and then a conversion reaction to form metallic Ag0 and MgS. The solid-state Mg2+ diffusion coefficients are as high as 3.6 × 10-9 and 3.1 × 10-10 cm2 s-1 for the intercalation and conversion reactions, respectively, which explains the high performance of the Ag2S cathode. This work provides scientific insights for the selection of a promising conversion cathode by the combination of soft anions and soft transition metal cations.