Nitrogen-doped multiwall carbon nanotubes (N-MWNTs) with different structures were synthesized by employing chemical vapor deposition and changing the argon/ethane/nitrogen gas precursor ratio and synthesis time, and broadband dielectric properties of their poly(vinylidene fluoride) (PVDF)-based nanocomposites were investigated. The structure, morphology, and electrical conductivity of synthesized N-MWNTs were assessed via Raman spectroscopy, scanning electron microscopy, transmission electron microscopy, thermogravimetric analysis (TGA), X-ray photoelectron spectroscopy, and powder conductivity techniques. The melt compounded PVDF nanocomposites manifested significantly high real part of the permittivity (ε') along with low dissipation factor (tan δ) in 0.1 kHz to 1 MHz frequency range, suggesting use as efficient charge-storage materials. Longer synthesis time resulted in enhanced carbon purity as well as higher thermal stability, determined via TGA analysis. The inherent electrical conductivity of N-MWNTs scaled with the carbon purity. The charge-storage ability of the developed PVDF nanocomposites was commensurate with the amount of the nitrogen heteroatom (i.e., self-polarization), carbon purity, and inherent electrical conductivity of N-MWNTs and increased with better dispersion of N-MWNTs in PVDF.