We investigate the magneto-optical properties of a nanostructured metamaterial comprised of arrays of nickel nanorods embedded in an anodized aluminum oxide template. The rods are grown using a self-assembly bottom-up technique that provides a uniform, quasi-hexagonal array over a large area, quickly and at low cost. The tuneability of the magneto-optic response of the material is investigated by varying the nanorod dimensions: diameter, length and inter-rod spacing as well as the overall thickness of the template. It is demonstrated that the system acts as a sub-wavelength light trap with enhanced magneto-optical properties occurring at reflectivity minima corresponding to photonic resonances of the metamaterial. Changes in dimensions of the nickel rods on the order of tens of nanometers cause a spectral blue-shift in the peak magneto-optical response of 270 nm in the visible range. A plasmonic enhancement is also observed at lower wavelengths, which becomes increasingly damped with larger diameters and increased volume fraction of nickel inclusions. This type of structure has potential applications in high density magneto-optical data storage (up to 1011–12 rods per square inch), ultrafast magneto-plasmonic switching and optical components for telecommunications.