Plasma etching of densely packed arrays of polystyrene particles leads to arrays of spherical nanostructures with adjustable diameters while keeping the periodicity fixed. A linear dependence between diameter of the particles and etching time was observed for particles down to sizes of sub-50 nm. Subsequent deposition of Co/Pt multilayers with perpendicular magnetic anisotropy onto these patterns leads to an exchange-decoupled, single-domain magnetic nanostructure array surrounded by a continuous magnetic film. The magnetic reversal characteristic of the film-particle system is dominated by domain nucleation and domain wall pinning at the particle locations, creating a percolated perpendicular media system.