Two Al alloys (AA1570 and AA6061) in the solutionized state have been processed by HPT at room temperature to achieve a homogeneous UFG structure. After HPT, the grain size was found to have a mean value about 100 nm for both alloys. Measured yield stress values of HPT-produced UFG alloys being plotted in terms of the Hall-Petch relationship were found to exceed the plot predictions for the range of ultrafine grain size. For both alloys, Atom Probe Tomography measurements allowed to reveal segregation of solute elements along grain boundaries. The origin of the extremely high strength of the alloys nanostructured by HPT is discussed with a special attention to the influence of such segregations on the emission and the mobility of dislocations.