Various flexible ethylene propylene diene monomer (EPDM)/paraffin wax (PW) vulcanizates with simultaneously increased mechanical strength, thermal energy storage (TES), and shape-memory behavior were prepared via the general meltblending method. Herein, the PW served as a phase-change working substance for TES applications and as a "hard phase" for shape fixation, and the vulcanized EPDM acted as a supporting material to avoid the leakage of PW and as a "soft phase" for shape recovery. Under the action of the vulcanizing agent, the gel loading of the EPDM component in the EPDM/PW blends increased from 42.0 to 96.0%, and the denser cross-link density provided excellent mechanical strength for the EPDM/PW vulcanizate. The melting and freezing latent heat of the EPDM/PW blend with 60.0 wt % PW (C60) were 123.5 and 121.8 J/g, respectively, and the melting and freezing relative enthalpy efficiencies of C60 were as high as 99.5 and 99.2%, respectively. In addition, C60 has good thermal reliability after 100 thermal cycles, excellent light-to-thermal energy storage, and shape-memory behavior. This study provides a strategy to prepare flexible shape-stable phase-change materials (SSPCMs) via melt-blending for large-scale preparation, and these proposed SSPCMs have a very high commercial value.