The influence of annealing on the microstructure and mechanical properties of ultrafine-grained (UFG) commercially pure aluminum preliminarily subjected to severe plastic deformation by high pressure torsion has been studied. It is found that annealing of the UFG samples in the temperature range 363–473 K for 1 h leads to increases in the conventional yield strength and ultimate tensile strength, which attained maximum values (50 and 30%, respectively) after annealing at 423 K. A key role of nonequilibrium high-angle grain boundaries in the strengthening effect of UFG-Al due to annealing is discussed. The increase in the strength of UFG-Al is accompanied by a significant decrease in its ductility. A new approach of increasing the ductility of UFG-Al with retaining a high strength is proposed. It is an introduction of additional dislocation density to a UFG structure relaxed by annealing.