In this work, stearic acid/carbon nanotubes composite phase change materials (SA/CNTs composite PCMs) were fabricated by ball milling for the first time to enhance the heat conduction of SA and prevent the delamination of SA and CNTs components. The results of suspension stability study conducted using a gravity sedimentation method showed that polyvinylpyrrolidone (PVP) used as dispersant has the best effect on the stability of composite PCMs. Then, the thermal cycling test further proved the stability of prepared composite. The SEM and FT-IR results revealed that ball milling led to the formation of highly homogeneous composites. The thermal properties of the fabricated SA/CNTs composites with CNTs contents of 2, 6, and 10 wt.% characterized by differential scanning calorimetry (DSC) demonstrated that their phase change temperatures varied slightly while the latent heat decreased with the increased CNTs content. Furthermore, the thermal conductivity of the SA/CNTs composites were greater than that of pure SA by 61.5%, 92.3%, and 119.2%, respectively. The addition of CNTs also increased the thermal release rates of the prepared PCMs and decreased their storage rates. Therefore, the produced materials can be potentially used in thermal management.