A patterned perpendicular magnetic recording medium of the type that has spaced-apart pillars with magnetic material on their ends and with nonmagnetic trenches between the pillars is made with a method that allows use of a pre-etched substrate. The substrate has a generally planar surface at the trenches and comprises material that when heated will diffuse into the magnetic recording layer material and chemically react with one or more of the elements typically used in the recording layer. The pillars are formed of material that will not diffuse into the recording layer. After the recording layer is formed over the entire substrate so as to cover both the pillar ends and the trenches, the substrate is annealed. This results in the destruction or at least substantial reduction of any ferromagnetism in the recording layer material in the trenches so that the trenches are nonmagnetic. The annealing does not affect the recording layer on the ends of the pillars because the pillars are formed of material that will not diffuse into the recording layer.