To have an insight into the occurrence of inverse Hall-Petch relationship in ultrafine-grained (UFG) aluminum alloys produced by severe plastic deformation (SPD), ultra-SPD (i.e. inducing several ten thousand shear strains via high-pressure torsion, HPT) followed by aging is applied to an Al-La-Ce alloy. Average nanograin sizes of 40 and 80 nm are successfully achieved together with strain-induced Lomer-Cottrell dislocation lock formation and aging-induced semi-coherent Al₁₁(La,Ce)₃ precipitation. Analysis of hardening mechanisms in this alloy compared to SPD-processed pure aluminum with micrometer grain sizes, SPD-processed Al-based alloys with submicrometer grain sizes and ultra-SPD-processed Al-Ca alloy with nanograin sizes reveals the presence of two breaks in the Hall-Petch relationship. First, a positive up-break appears when the grain sizes decrease from micrometer to submicrometer which is due to extra hardening by solute-dislocation interactions. Second, a negative down-break and softening occur by decreasing the grain sizes from submicrometer to nanometer which is caused by weakening the dislocation hardening mechanism with minor contribution of the inverse Hall-Petch mechanism. Detailed analyses confirm that nanograin formation is not necessarily a solution for extra hardening of Al-based alloys and other accompanying strategies such as grain-boundary segregation and precipitation are required to overcome such a down-break and softening.