Epoxy matrix nanocomposites with nickel nanoparticles of two different sizes were processed and characterized to investigate their structure-magnetic property correlations. Crystal structure, morphology, density, resistivity and magnetic properties of the nanocomposites with different filler contents were compared for different size scales. Nanocomposites with 25 nm nanoparticles showed higher coercivity, higher frequency stability and lower loss, though the permeability was suppressed. Coarser nickel particles (100 nm) showed a permeability of ~5.5 but stability only up to 200 MHz. The structure-magnetic property correlations were validated using analytical models to provide valuable design guidelines for permeability and frequency-stability in particulate nanocomposites.