Macro-encapsulated phase change material (PCM) capsules are the core components that form the heat storage tank of the packed bed. In order to enhance the heat storage rate of the packed bed tank, it is necessary to optimize the heat storage and discharge rate of individual PCM capsules. Four different encapsulated shapes of PCM capsules were established while ensuring the uniform volume of individual PCM capsules. The capsules were placed in a flow field with an obstruction rate of 0.5, and the melting and solidification processes of PCM under different encapsulation shapes were analyzed with full consideration of gravity direction and heat transfer fluid flow direction in practical applications. The results show that the natural convection of liquid PCM inside the capsule can accelerate the melting and solidification process of PCM and increase the rate of heat storage and exotherm; compared with the spherical encapsulation capsule, the heat transfer area per unit volume of cylindrical encapsulation capsule is increased by 14.47% and the melting time of PCM is shortened by 42.50%. Therefore, the cylindrical encapsulated capsule has the best thermal performance, and the cylindrical capsule can be applied to the packed-bed storage tank in future research to optimize its thermal storage performance.