Using molecular dynamics simulation, a study of the melting of aluminum with a nanocrystalline structure obtained as a result of severe plastic deformation was conducted. It is shown that the melting of nanocrystalline aluminum begins at a lower temperature than monocrystalline aluminum. The higher the density of grain boundaries and other defects, and, accordingly, the higher the excess energy, the lower the melting temperature. In the presence of defects, melting proceeds heterogeneously and begins primarily from the grain boundaries and free surface. In a pure crystal that did not contain any defects or free surface, melting in the model proceeded homogeneously. When studying recrystallization in nanocrystalline aluminum, it was found that its intensity is greatly influenced by the free surface: the restructuring of the structure near it occurred faster than in the bulk of the material.