Strain-controlled low cycle fatigue (LCF) tests were conducted on conventionally grained (CG) and ultrafine-grained (UFG) Al-Mg-Si alloys treated under various aging conditions. In the cyclic stress response (CSR) curves, CG peak-aged (PA) alloys showed initial cyclic hardening and subsequent saturation, whereas CG over-aged (OA) alloys displayed cyclic softening behavior close to saturation. The UFG materials exhibited continuous cyclic softening except for UFG 3; it originates from the microstructural stability of the UFG materials processed by severe plastic deformation (SPD). Using a strain-based criterion, the LCF behavior and life of the CG and UFG materials were analyzed and evaluated; the results are discussed in terms of strengthening mechanisms and microstructural evolution. In the CG materials, the LCF life changed markedly owing to differences in deformation inhomogeneity depending on the precipitate state. However, the UFG materials displayed a decreasing LCF life as cyclic softening induced by dynamic recovery became more severe; additionally, a relationship between the microstructural stability of the UFG materials and the cyclic strain hardening exponent n′ was suggested.