Molecular dynamics simulations were used to investigate the size-dependent melting mechanism of nickel nanoclusters of various sizes. The melting process was monitored by the caloric curve, the overall cluster Lindemann index, and the atomic Lindemann index. Size-dependent melting temperatures were determined, and the correct linear dependence on inverse diameter was recovered. We found that the melting mechanism gradually changes from dynamic coexistence melting to surface melting with increasing cluster size. These findings are of importance in better understanding carbon nanotube growth by catalytic chemical vapor deposition as the phase state of the catalyst nanoparticle codetermines the growth mechanism.