In plastically deformed coarse-grained metallic materials, recovery annealing largely decreases their strength because of the annihilation of the stored dislocations. In contrast, the subsequent grain growth only slightly decreases their strength. We have found an exactly opposite change in the strength of our annealed nanocrystalline iron- and nickel-based alloys prepared by a severe plastic deformation method – mechanical alloying. In the recovery stage, the microhardness is almost constant and even slightly increases just before the grains start to grow because of the segregation of solutes in the grain boundary. Our experiment results suggest that the dislocations – mainly taking the form of dislocation dipoles – stored in the grain interiors of our mechanically alloyed nanocrystalline alloys do not influence the microhardness. At the grain growth stage, microhardness decreases as the grains grow. In addition, the microhardness of furnace-cooled nanocrystalline alloys is higher than that of air-cooled nanocrystalline alloys, further supporting that the grain boundary segregation influences the microhardness of nanocrystalline alloys. Our experimental results suggest that it is the grain size and the grain boundary structure, rather than the dislocations stored in the grain interiors, that determine the strength of the deformed and annealed nanocrystalline alloys.