A generalization of the Hall-Petch relationship is proposed. The generalized relationship takes account of the contributions from intergrain sliding, generation of lattice dislocations, and influence of disclination-like defects. From this approach, a critical size corresponding to a maximum of the Hall-Petch size dependence is obtained. The value of the critical size essentially depends on the state of boundaries and it explains contradictory results for the microhardness of nanocrystals (NCs), since grain-boundary sliding is facilitated in unrelaxed nanocrystals and constrained in aged ones.