Paraffin phase change materials (PCMs) exhibit great potential in battery thermal management (BTM); nevertheless, their application has been hampered by the handicap of low thermal conductivity, leakage, and volume expansion during phase transition. In this work, ternary composite PCMs formed of paraffin, expanded graphite (EG), and low-density polyethylene (LDPE) were developed for application in BTM. The structure and properties of the composite PCMs were characterized via X-ray diffraction, scanning electron microscopy, differential scanning calorimetry, and thermal constant analysis. The result shows that EG can form a large-size graphite frame as heat conduction paths to improve the thermal conductivity of the composite PCM, and LDPE can form an interpenetrating network within the composite PCM to resist the internal stress of paraffin expansion and prevent deformation. The latent heat and thermal conductivity of the composite PCMs loaded with 10 wt% EG and 4 wt% LDPE can reach 172.06 J/g and 3.85 Wm−1K−1 with a relatively low leakage ratio of 6.2 wt%. Remarkably, the composite PCMs could reduce the temperature rise of the battery by 55.1%. In brief, this work provides a feasible route to develop high-performance PCMs for BTM.