The shape of container influences natural convection inside a latent heat storage with a phase change material (PCM). Often, the geometrical design of a PCM container is based on empirical observations. To enhance convection and melting of the PCM, authors propose here new design guidelines for an improved container. Using the so-called Co-factor method as the optimized basis, which is defined as the vector product of the velocity and temperature gradient, the new design method strives to raise the velocity of natural convection in liquid PCM, increase the amount of PCM in the direction of the convective flow, and reduce the amount of PCM far from the heating surface. Following these guidelines and Co-factor, an optimized PCM container with an elongated and curved shape is proposed and compared with a rectangular container. Numerical simulations indicated that the total melting time of the PCM in the optimized container could be reduced by more than 20% compared with the rectangular one. The higher natural convection velocity and the better use of it to melt the PCM in the optimized container space attributed to the better performance than that in rectangular container. The results can be used to design more effective PCM storage systems.