We observe that a nanostructured metal can be hardened by annealing and softened when subsequently deformed, which is in contrast to the typical behavior of a metal. Microstructural investigation points to an effect of the structural scale on fundamental mechanisms of dislocation-dislocation and dislocation-interface reactions, such that heat treatment reduces the generation and interaction of dislocations, leading to an increase in strength and a reduction in ductility. A subsequent deformation step may restore the dislocation structure and facilitate the yielding process when the metal is stressed. As a consequence, the strength decreases and the ductility increases. These observations suggest that for materials such as the nanostructured aluminum studied here, deformation should be used as an optimizing procedure instead of annealing.