The effect of preliminary and post-deformation heat treatment on structure and hardness of severely deformed aluminum alloy D16 was investigated. Pre-quenched and aged at 190 °C from 1 to 10 hrs alloy was subjected to high pressure torsion (HPT) (N=10 turns, P=6 GPA, T=20 °C), and then to re-aging at 100 °C up to 100 hrs. Despite of ~ 40 HV increase in the alloy hardness at aging before HPT and also reduction in development of the nanostructure under HPT, hardness of all deformed conditions was close and reached 260±10 HV. It was found that re-aging was quite effective for all the alloy states, except peakaged one, to increasing their hardness on 20-50HV with maximum after 50 hrs in pre-quenched alloy. The nature of the alloy structural and mechanical behavior was discussed in detail.