In this study, a novel composite of Fe3O4 nanofiller-decorated single-layer graphene-assembled porous carbon (SLGAPC) with polyvinyl alcohol (PVA) having flexibility and a density of 0.75 g cm(-3) is explored for its dielectric and electromagnetic interference (EMI) response properties. The composite is prepared by the solution casting method and its constituents are optimized as 15 wt% SLGAPC and 20 wt% Fe3O4 through a novel solvent relaxation nuclear magnetic resonance experiment. The PVA-SLGAPC-Fe3O4 composite shows high dielectric permittivity in the range of 1 Hz-10 MHz, enhanced by a factor of 4 as compared to that of the PVA-SLGAPC composite, with a reduced loss by a factor of 2. The temperature dependent dielectric properties reveal the activation energy behaviour with reference to the glass transition temperature (80 °C) of PVA. The dielectric hysteresis with the temperature cycle reveals a remnant polarization. The enhanced dielectric properties are suggested to be the result of improvement in the localized polarization of the integrated interface system (Maxwell-Wagner-Sillars (MWS) polarization) formed by the uniform adsorption of Fe3O4 on the surface of SLGAPC conjugated with PVA. The EMI shielding property of the composite with a low thickness of 0.3 mm in the X-band (8.2-12.4 GHz) shows a very impressive shielding efficiency of ∼15 dB and a specific shielding effectiveness of 20 dB (g cm(-3))(-1), indicating the promising character of this material for flexible EMI shielding applications.