Provided is a method of producing a multivalent metal-ion battery comprising an anode, a cathode, and an electrolyte in ionic contact with the anode and the cathode to support reversible deposition and dissolution of a multivalent metal, selected from Ni, Zn, Be, Mg, Ca, Ba, La, Ti, Ta, Zr, Nb, Mn, V, Co, Fe, Cd, Cr, Ga, In, or a combination thereof, at the anode, wherein the anode contains the multivalent metal or its alloy as an anode active material and the cathode comprises a cathode active layer of graphitic carbon particles or fibers that are coated with a protective material. Such a metal-ion battery delivers a high energy density, high power density, and long cycle life.