A nanocomposite with ultra-low percolation threshold and high dielectric performance is prepared by controlling the localization of multiwalled carbon nanotubes (MWNTs) in one phase of a ternary continuous polymer blend system through melt processing. Polystyrene (PS), poly(vinylidene fluoride) (PVDF), and poly(methyl methacrylate) (PMMA) can form a ternary continuous structure when the volume fractions of PS, PVDF and PMMA are 70 vol%, 20 vol%, and 10 vol%, respectively. The PS is a continuous matrix (sea-phase) whereas the other two phases are interconnected threads (the PVDF is situated as the core while the PMMA is the shell, and the thickness of the PMMA shell is about 1 μm). Adding PMMA could improve the compatibility between the PS and PVDF components. Selective distribution of MWNTs in the PMMA shell is achieved through a combination of PMMA modified MWNTs and appropriate processing procedures. The composite shows an ultra-low percolation threshold of ca. 0.3 wt%. When the weight fraction of PMMA modified MWNTs is 0.4 wt%, the dielectric constant of the composite is as high as 182 (at 100 Hz), which is about 60 times higher than that of a pure PS matrix. The composite’s dielectric properties have excellent temperature stability. This approach can provide a new and low-cost route to design high-performance dielectric materials with ultra-low percolation thresholds.