In recent years, phase change materials (PCMs) have been presented as a suitable alternative for thermal energy storage (TES) systems for solar water heater (SWH) applications. However, PCMs’ low thermal conductivity and the high dependence on external conditions are the main challenges during the design of TES systems with PCMs. Design actions to improve the performance of the TES systems are crucial to achieve the necessary stored/released thermal energy and guarantee the all-day operation of SWHs under specific system requirements. In this study, a TES with PCM in the configuration of a heat exchanger was redesigned, focused on achieving two main targets: an outlet water temperature over 43 °C during discharging time (15 h) and efficiency over 60% to supply the hot water demand of two families (400 L). A four-step redesign methodology was proposed and implemented through numerical simulations to address this aim. It was concluded that the type, encapsulation shape, and amount of PCM slightly impacted the system’s performance; however, selecting a suitable sensible heat storage material had the highest impact on meeting the system’s targets. The redesigned TES reached 15 operating hours with a minimum outlet water temperature of 45.30 °C and efficiency of 76.08%.