A heat-assisted magnetic recording medium that includes a substrate 1, underlayers formed on the substrate 1, and a magnetic layer 5 which is formed on the underlayers and contains either an FePt alloy having an L10 structure or a CoPt alloy having an L10 structure as a main component, wherein the underlayers include a first underlayer 2 formed from an amorphous alloy, a second underlayer 3 formed from an alloy having a BCC structure containing Cr as a main component and also containing at least one element selected from among Ti, Mo, W, V, Mn and Ru, and a third underlayer 4 formed from MgO. Also, a magnetic storage device that uses the heat-assisted magnetic recording medium.