We suggest a model, which describes the effect of grain boundary relaxation on the annealing-induced hardening in ultrafine-grained metals. Within the model, grain boundary relaxation during annealing is accompanied by a decrease in the number of grain boundary dislocation sources. The exhaustion of easily activated grain boundary dislocation sources results in the activation of harder grain boundary dislocation sources and/or repetitive action of the same dislocation sources. This gives rise to an increase in the strain hardening rate that can lead to an increase in the ultimate strength of ultrafine-grained solids. The results of the model agree with available experimental data.