A composite phase change material (PCM) was prepared by incorporating paraffin (PA) with expanded graphite (EG) and nano-metal particles to improve the thermal conductivity and reduce the leakage performance of PA once it melts and, consequently, develop a more efficient PCM for a personal phase change cooling system. A series of experiments was carried out by a scanning electron microscope, a differential scanning calorimeter, a hot-disk thermal analyzer, and leakage tests on the composite PCM with various mass fractions of EG and metals (i.e., Cu, Al, Ni, and Fe). Through comprehensive consideration of the thermal conductivity, leakage, and homogeneity, a composite PCM with the optimal proportion (PA-EG11%-Cu1.9%) was screened out. Its thermal conductivity was significantly improved nine times, while the phase change enthalpy showed a minimal decrease. In addition, the relationships of the composite PCM with its temperature and density were systematically investigated. The experimental results are important for determining the proper package density of PCM for application into a personal cooling system because its weight is crucial for the system design and benefits the performance comparison of various PCMs prepared under various conditions. Lastly, the heat storage efficiency of the PA–EG–Cu material was investigated using heat storage tests. Cooling performance clearly improved compared to the PCM without nano-particles added.