The influence of low temperature annealing and subsequent deformation on microstructure, strength and ductility was investigated for the first time for high pressure torsion (HPT) processed commercially pure Al. Extremely high increases in the conventional yield stress (up to 50%) and ultimate tensile strength (up to 30%) were obtained by annealing of the ultrafine grained (UFG) samples in the range 90–200 °C for 1 h. Such increases were accompanied by a sharp drop in ductility up to 1%. Implementation of high ductility at the level of coarse-grained Al, while maintaining high strength of the HPT-processed sample was demonstrated for the first time and achieved by repeating the low temperature annealing followed by subsequent additional HPT deformation. The key role of relaxation of non-equilibrium high-angle grain boundaries (GBs) in the strengthening effect of UFG-Al by annealing is shown. Two theoretical models are suggested to explain the hardening by annealing and the implementation of high ductility in UFG structures. Within the models, plastic deformation occurs through emission of lattice dislocations from triple junctions of GBs containing pile-ups of grain-boundary dislocations, glide of the lattice dislocations across neighboring grains, their accumulation at and climb along the opposite GBs. The energy characteristics and the critical stresses of dislocation emission are determined in two different cases, for UFG Al subjected to annealing only and to annealing with subsequent additional HPT deformation. The calculated theoretical dependences of the flow stress on the plastic deformation value well fit qualitatively and quantitatively to our experimental data.