The thermal performance and response time of Thermal Energy Storage (TES) units are mainly limited by the enclosure design and the low thermal conductivity of the storage medium. In the present study, the performance of petal-shape pipes in a shell and tube TES unit was numerically modeled and analyzed. The integration of the finite element method, a mesh adaptation approach, and an adaptive time-step scheme, was used to robustly simulate the phase change process and energy storage in the TES unit. The enclosure was considered fixed both dimensionally and by volume, which acts as a design constraint. The impacts of using two types of nano-additives, Cu and GO nanoparticles, and the geometrical aspects of the petal pipe on the thermal behavior of the TES unit were investigated. To find the optimal design of the TES unit with the maximum thermal energy power, the Taguchi optimization method was employed and a sensitivity analysis was performed. The copper nano-additives showed a better performance than the graphene oxide nano-additives. Although the surface area of the petal-pipe was fixed, its geometric shape was the most important parameter for maximizing the energy storage power of the TES unit. The optimum design could improve the amount of storage energy by 23.3% (Cu) and 22.5% (GO) NePCM compared to average designs. Based on an ANOVA analysis, the amplitude of petal shape could influence the total energy storage with a contribution ratio of about 41%, while the nanoparticles' contribution was 5–6%. An optimal design of a petal tube and Cu nanoparticles could improve the heat transfer by 45% compared to a circular tube with no nanoparticles.