Nano-enhanced phase change materials are highly employed for an enhanced heat-transfer process. The current work reports that the thermal properties of solar salt-based phase change materials were enhanced with carbon nanotubes (CNTs). Solar salt (60:40 of NaNO3/KNO3) with a phase change temperature and enthalpy of 225.13 °C and 244.76 kJ/kg, respectively, is proposed as a high-temperature PCM, and CNT is added to improve its thermal conductivity. The ball-milling method was employed to mix CNTs with solar salt at various concentrations of 0.1, 0.3, and 0.5% by weight. SEM images display the even distribution of CNTs with solar salt, with the absence of cluster formations. The thermal conductivity, phase change properties, and thermal and chemical stabilities of the composites were studied before and after 300 thermal cycles. FTIR studies indicated only physical interaction between PCM and CNTs. The thermal conductivity was enhanced with an increase in CNT concentration. The thermal conductivity was enhanced by 127.19 and 125.09% before and after cycling, respectively, in the presence of 0.5% CNT. The phase change temperature decreased by around 1.64% after adding 0.5% CNT, with a decrease of 14.67% in the latent heat during melting. TGA thermograms indicated the weight loss was initiated at about 590 and 575 °C before and after thermal cycling, after which it was rapid with an increase in temperature. Thermal characterization of CNT-enhanced solar salt indicated that the composites could be used as phase change materials for enhanced heat-transfer applications.