We have investigated the work softening (WS) phenomena during a cold-roll process of an AlFe alloy, based on hardness measurements, electron microscopy observations, and thermodynamic calculations. The WS behavior was confirmed in the AlFe alloy when the rolling rate was larger than 80%, which contained fine grains with severe deformation. In contrast, the behavior and microstructural features were hardly observed in the A1050 alloy. Composition analyses showed that almost all Fe in the present AlFe alloy form the ª-Al13Fe4 phase, in which a trace impurity element, Si, is found to be significantly segregated. This Si partitioning behavior is confirmed by the thermodynamic calculations and consequently leads to a higher purification of the relevant Al matrix as being almost close to the 4N (99.99 mol%) level, known as a “scavenging effect” of the impurities. It can be concluded that the highly purified aluminum matrix provides an intrinsic origin of the WS of the present AlFe alloy. Significant reductions of the impurities may lead to an extended mean-free path of dislocation motions and related grain boundary effects, which promote the occurrence of dynamic recovery and/or recrystallizations at severe deformation ranges even during the cold-roll process.