Novel permittivity gradient (ε-G) composites based on surface treated multi-walled carbon nanotubes (eMCNTs) and cyanate ester (CE) resin were successfully developed by the gravity sedimentation method. The composites consisting of original multi-walled carbon nanotubes (MCNTs) and CE resin, coded as MCNT/CE, were also prepared for comparison. Each composite was cut into three slices in the direction of thickness for evaluating the difference of dielectric properties over a wide frequency range from 1 to 109 Hz between the whole composites and their slices. Results show that the surface treatment of MCNTs is necessary to form ε-G composites because the good dispersion of nanotubes in the resin matrix and the attractive interfacial adhesion between nanotubes and the matrix are key aspects for guaranteeing the gradient distribution of the concentration of nanotubes in the composites. Note that two interesting phenomena were discovered. First, the whole composites show different conductive and dielectric properties from their slices, specifically, the percolation effect does not appear in either whole eMCNT/CE or MCNT/CE composites, while it can be observed in their slices. In addition, the percolation threshold of the eMCNT/CE slice is about 25% lower than that of the MCNT/CE slice. Second, with regard to the whole composite and its slice with the same content of nanotubes, they have a similar dielectric constant, but the dielectric loss factor of the former is remarkably larger than that of the latter; these differences in properties are attributed to the different space distribution of the concentration of nanotubes between the whole composites and slices. These attractive features of eMCNT/CE composites suggest that the method proposed herein is a new approach to develop high performance ε-G composites, especially those with high dielectric constant and extremely low dielectric loss for cutting-edge industries.