Microscopic understanding of thermal behaviors of metal nanoparticles is important for nanoscale catalysis and thermal energy storage applications. However, it is a challenge to obtain a structural interpretation at the atomic level from measured thermodynamic quantities such as heat capacity. Using first-principles molecular dynamics simulations, we reproduce the size-sensitive heat capacities of Al-N clusters with N around 55, which exhibit several distinctive shapes associated with diverse melting behaviors of the clusters. We reveal a clear correlation of the diverse melting behaviors with cluster core symmetries. For the Al-N clusters with N = 51-58 and 64, we identify several competing structures with widely different degree of symmetry. The conceptual link between the degree of symmetry (e.g., T-d, D-2d, and C-s) and solidity of atomic clusters is quantitatively demonstrated through the analysis of the configuration entropy. The size-dependent, diverse melting behaviors of Al clusters originate from the reduced symmetry (T-d -> D-2d -> C-s) with increasing the cluster size. In particular, the sudden drop of the melting temperature and appearance of the dip at N = 56 are due to the T-d-to-D-2d symmetry change, triggered by the surface saturation of the tetrahedral Al-55 with the T-d symmetry.