A magnetic recording medium that uses, as a protective coating layer provided on a magnetic layer for magnetically recording signals, a layer made of a nonmagnetic material consisting of two ore more elements of Ti, Zr, Hf, V, Nb, Ta, Cr, Mo, and W, and one or more elements of N, C, O, and B, or made of a magnetic material consisting of one or more elements of Co, Fe, Ni, and Gd, one or more elements of Ti, Zr, Hf, V, Nb, Ta, Cr, Mo, and W, and one or more elements of N, C, O, B, and Si is excellent in sliding endurance. When the protective coating layer is made of the nonmagnetic material, the magnetic recording medium is also excellent in corrosion resistance, and when the protective coating layer is made of the magnetic material, the spacing between a magnetic head and the magnetic recording medium can advantageously be made large. Both the cases are high in reliability, and suitable for high density magnetic recording. The magnetic recording medium can be used in combination with a magnetic head that uses a metal magnetic alloy as at least part of the magnetic core to provide an excellent magnetic storage.