Ultrafine-grained Al alloys produced by high-pressure torsion are found to exhibit a very high strength, considerably exceeding the Hall-Petch predictions for ultrafine grains. This phenomenon can be attributed to the unique combination of ultrafine structure and deformation-induced segregations of solute elements along grain boundaries, which may affect the emission and mobility of intragranular dislocations.