Understanding the melting mechanisms of nanocrystals embedded in solids is of great current interest since both the synthesis and modification of such systems frequently involve the use of high temperatures. Using molecular-dynamics computer simulations we study the melting mechanisms of Cu, Ag, and Au nanoclusters embedded in metal matrices and Si nanocrystals in amorphous silica. The results show that nanocrystals embedded in a solid bulk material with a higher melting temperature exhibit complex melting behavior and can even, in the same system, exhibit four distinct stages prior to full melting of the system.