The effect of melting temperature on the Hall-Petch relationship has been studied. As grain size decreases, the melting temperature of the nano-structured crystals also decreases, therefore the Hall–Petch relationship has its limitation and is no longer sufficient when the grain size decreases to about the 15-30 nm range. When the yield strength or hardness is taken as a function of the reciprocal of the square root of the grain size, it has a numerical maximum whose location depends on the size of the bulk melting enthalpy of the crystals. Experimental results agree well with the modification induced by the size-dependence. In addition, the appropriate size range for the classic Hall-Petch relationship is discussed in terms of the modification of the relationship.