Effective thermal conductivity and phase change properties of paraffin wax-based nanocomposites with multi-walled carbon nanotubes are experimentally investigated in this paper. It has been observed that the thermal conductivity enhancement achieved by a small amount of nanotubes is much higher than that predicted by theoretical models. However, the most striking results obtained concern the phase change behavior of the composites. Indeed, a significant rise of the latent heat of the composite compared to that of the paraffin wax has been observed. Moreover, the latent heat increases linearly with the amount of nanotubes added. Several factors might account for these results and are discussed in the paper.