A heat-assisted magnetic recording medium that includes a substrate, underlayers formed on the substrate, and a magnetic layer 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 formed from an amorphous alloy, a second underlayer 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 formed from MgO. Also, a magnetic storage device that uses the heat-assisted magnetic recording medium.