Colloidal nanocrystals are a technologically important class of nanostructures whose phase change properties have been largely unexplored. Here we report on the melting behavior of In, Sn, and Bi nanocrystals dispersed in a polymer matrix. This polymer matrix prevents the nanocrystals from coalescing with one another and enables previously unaccessed observations on the melting behavior of colloidal nanocrystals. We measure the melting temperature, melting enthalpy, and melting entropy of colloidal nanocrystals with diameters of approximately 10 to 20 nm. All of these properties decrease as nanocrystal size decreases, although the depression rate for melting temperature is comparatively slower than that of melting enthalpy and melting entropy. We also observe an elevated melting temperature during the initial melt-freeze cycle that we attribute to surface stabilization from the organic ligands on the nanocrystal surface. Broad endothermic melting valleys and very large supercoolings in our calorimetry data suggest that colloidal nanocrystals exhibit a significant amount of surface pre-melting and low heterogeneous nucleation probabilities during freezing.