Blast furnace slag (BFS), one kind of typical solid waste in the steel industry, was used as structural materials to synthesize NaNO3/BFS composite phase change materials (C-PCMs) by mixing and sintering method. NaNO3 in the composites functioned as phase change materials (PCMs) and BFS as structural skeleton to maintain a stable external form. In this study, the prepared C-PCMs could remain in the solid state without salt leakage even if operating temperature exceeded the melting temperature of NaNO3. The composition and structure of BFS and the prepared composites were characterized by XRD, FTIR, SEM and TG-DSC analyses. The results showed that NaNO3 was well incorporated in the pores of BFS. The melting temperature and latent heat of the final composites were 300.5 °C and 65.53 J/g, respectively. The product also had good thermal storage performance and durability even after 100 thermal cycles. The energy densityEnergy Density of the product was calculated as high as 468.03 J/g for an temperature range of 50–400 °C.