The microwave permittivity of multi-walled carbon nanotubes blended in paraffin wax has been studied in the frequency range from 2 to 18GHz. The dissipaton factors of the multi-walled carbon nanotubes are high at the microwave frequencies. The microwave permittivity of the multi-walled carbon nanotubes and paraffin wax (or other dielectric materials) composites can be tailored by the content of the carbon nanotubes. And ε′, ε″and tgδ of the composites increase with the volume filling factor (v) of the carbon nanotubes. The ε′ and ε″ of the multi-walled carbon nanotubes decrease with frequency in the frequency range from 2 to18 GHz. This property is very good for broadband radar absorbing materials. The classical effective medium functions can not effectively model the microwave permittivities of the composites containing multi-walled carbon nanotubes. The ε′ and ε″ can be effectively modeled using second-order polynomials (ε′, ε″=Av2+Bv+C). The high ε″ and dissipation factor tgδ (ε″/ε′) of multi-walled carbon nanotubes are due to the dielectric relaxation. The carbon nanotubes composites would be a good candidate for microwave absorbing material electromagnetic interface (EMI) shielding material.