Although the melting of ice is an everyday process, important issues remain unclear particularly on the nanoscale. Indeed despite extensive studies into ice melting and premelting, little is known about the relationship between (pre)melting and crystal size and morphology, with, for example, the melting temperature of ice nanocrystals being unclear. Here we report extensive long-time force-field-based molecular dynamics studies of the melting of hexagonal ice nanocrystals in the ca. 2 to 8 nm size range. We show that premelting is initiated at the corners of the crystals, then the edges between facets, and then the flat surfaces; that is, the melting temperature is related to the degree of coordination. A strong size dependence of the melting temperature is observed, with the combination of small particle size and premelting leading nanosized ice crystals to have liquid-like surfaces as low as about 130 K below the bulk ice melting temperature. These results will be of relevance in understanding the size dependence of ice crystal morphology and the surface reactivity of ice particles under atmospheric conditions.