Rechargeable non-lithium-ion (Na(+), K(+), Mg(2+), Ca(2+), and Al(3+)) batteries have attracted great attention as emerging low-cost and high energy-density technologies for large-scale renewable energy storage applications. However, the development of these batteries is hindered by the limited choice of high-performance electrode materials. In this work, MXene nanosheets, a class of two-dimensional transition-metal carbides, are predicted to serve as high-performing anodes for non-lithium-ion batteries by combined first-principles simulations and experimental measurements. Both O-terminated and bare MXenes are shown to be promising anode materials with high capacities and good rate capabilities, while bare MXenes show better performance. Our experiments clearly demonstrate the feasibility of Na- and K-ion intercalation into terminated MXenes. Moreover, stable multilayer adsorption is predicted for Mg and Al, which significantly increases their theoretical capacities. We also show that O-terminated MXenes can decompose into bare MXenes and metal oxides when in contact with Mg, Ca, or Al. Our results provide insight into metal ion storage mechanisms on two-dimensional materials and suggest a route to preparing bare MXene nanosheets.