Novel binary shape-stabilized composite phase change materials (CPCMs) have been successfully prepared using a crosslinked polyurethane (PU) copolymer with a solid–solid phase transition as the supporting framework for loading additional (‘free’) poly(ethylene glycol) (PEG). The PU copolymer was synthesized by a two-step method using 2-hydroxypropyl-β-cyclodextrin (Hp-β-CD) as a chain extender and PEG as a soft segment. The composition, morphology, phase transition behavior and thermal properties of the prepared CPCMs have been elucidated by a wide range of techniques. Investigation of FTIR spectra and SEM images reveal that the ‘free’ PEG and the PU copolymer network within the CPCMs have good compatibility and high affinity due to the noncovalent interactions. Polarized light optical microscopy shows that the CPCMs produce smaller spherulites than pristine PEG, and homogeneous nucleation was prevalent during the crystallization process. Due to the dual-phase transition of the CPCMs (the solid–liquid phase transition of ‘free’ PEG and solid–solid phase transition of the PU matrix) occurring within the same, narrow temperature window, the CPCMs have far higher heat storage density compared with that of traditional shape-stabilized PCMs with the same ‘free’ PEG content. Importantly, thermal cycling and thermogravimetric analyses show that the CPCMs have good reusability and excellent thermal stability for potential use in thermoregulation or energy storage applications.