Energy-intensive industries contribute large amounts of greenhouse gas emissions. An effective strategy to decarbonise these industries is by applying process integration tools to enhance energy efficiency and reduce overall energy consumption. Recent studies showed that thermal energy storage offers significant benefits in energy efficiency enhancement, as it can amplify the energy recovery potential. Despite its potential, studies that applied process integration tools to address heat recovery problems with consideration of heat storage remain limited. This work develops an optimisation framework that aims to determine optimal heat storage type and size based on the total annualised cost (i.e., costs associated with storage facilities and utilities) to form a feasible heat recovery network between plants. The proposed framework is demonstrated through a case study that focuses on optimising the sensible heat storage selection for indirect heat integration between a mixed plastic waste treatment plant and a steel mill. By analysing the performance and effectiveness of the storage media studied, nitrate salt storage medium is selected due to its greatest energy and cost savings of 12.7 % and 20.7 %, when compared to direct Heat Integration. Insights from this provide information on the feasibility of implementing a storage-supported heat recovery network in the energy-intensive industry.