A three-phase composite with multi-walled carbon nanotubes (MWNTs) and BaTiO3 particles embedded into polyvinylidene fluoride was prepared by using a simple blending and hot-molding technique. The dielectric measurement results show that the effective dielectric constant of the composite is slightly dependence on the frequency below 1 MHz but increases rapidly with the MWNTs concentration when the concentration is very close to the percolation threshold. The temperature has a little effect on the variation of the dielectric behavior. The percolation theory is used to explain the experimental results.