A bulk Al–4 mass% Fe alloy processed by extrusion or by a combination of extrusion and successive annealing was subjected to severe plastic deformation (SPD) through high-pressure torsion (HPT) for up to 75 revolutions. Microstructural evolution was examined by optical microscopy and transmission electron microscopy with special attention for the grain refinement in the Al matrix and for the distribution and morphology of Fe-containing intermetallic particles. Solubility of Fe in the Al matrix was studied by X-ray diffraction (XRD). A significant increase in Vickers microhardness was observed because of the development of an ultrafine-grained matrix and a fine fragmentation of the intermetallic particles especially at an early stage of SPD. The strengthening was affected by the initial state of the microstructure prior to HPT, but finally it was saturated at a higher degree of straining.