The effect of post-process deformation on the mechanical properties of nanostructured aluminum (99.2% purity) has been investigated by cold rolling of samples which have been processed by accumulative roll bonding (ARB) to a strain of epsilon(vM) = 4.8. Samples have been cold rolled to 10, 15, and 50% reductions and ultimate tensile strength (UTS), yield stress and elongation have been determined by tensile testing at room temperature. The mechanical testing shows that cold rolling to low strains (10% and 15%) leads to softening and increase in elongation compared to the as-processed ARB material. In contrary, cold rolling to large strain (50%) results in significant strengthening. This leads to the suggestion of a transition strain within the range of 25-35% reduction by rolling. The microstructural evolution during post-process deformation has been followed by transmission electron microscopy showing a significant change in the dislocation structure when the strain is increased. Based on the experimental observations the mechanical behavior is related to the structural changes focusing on the characteristics of the dislocation structure present between the narrowly spaced lamellar boundaries in the deformed structure.